스택에는 현재 인덱스 i를 집어넣는다. 그 전에 스택이 비어있지 않으면 스택의 최상단(위치 prev)과 현재 높이(위치 i)의 차이 -1(자기자신은 빼줌) 개수 만큼의 빌딩을 볼 수 있다는 이야기이다. n=80000이고 자기 위치 다음 빌딩들이 모두 자기보다 작다하면 80000+ 79999 + 79998 +... 이런 예시가 들어온다 대략 n^2으로 계산하면 6.4*10^9 으로 int 범위가 넘어가므로 ans는 long long 형으로 해준다. #include #include #include #include using namespace std; int n; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; vector v(n)..
www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net O(n)시간으로 현재 위치 수보다 더 큰 수를 찾는 문제 스택으로 푸는 걸 알고있어서 구현은 금방했는데도 시간 초과가 나서 헤맸다. 배열을 모두 출력할 때 모두 system.out을 쓰기보다 Stringbuilder로 문자열로 만든 다음에 한 번 출력해야 시간초과가 나지 않는다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStr..
www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 구현인데 어려웠다 괄호가 코딩테스트에 자주 나오는 이유 ~ 중첩된 것의 계산을 어떻게 해줄지 떠올리느냐 아니냐가 중요했다 나의 경우 괄호의 깊이를 계산해서 후위계산식으로 만들어서 계산해줄려고 했는데 너무 길고 복잡해서 다른 사람 풀이를 참고 했다. --- 중첩되어서 안쪽에 있는 괄호쌍은 앞에서 곱해온 수에 현재 괄호쌍의 값을 곱한다. 여는 괄호에서 곱해주면 된다. ( 열 때마다 중첩되서 깊어지므로) 만약 현재..