곽로그

문제 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 풀이 1. 순회 (시간초과) - 오큰수를 순회로 풀면 시간 초과가 난다. 즉 수열을 순회하면서 index번째 수의 오큰수를 구할 때, 다시 index+1 부터 순회를 하게되면 시간 복잡도는 N제곱이 되어서 시간초과가 난다. 2. 스택이용 - A의 오큰수 B를 구하는 게 아닌, B가 어떤 수의 오큰수가 되는지를 역으로 구해야한다. - B가 A의 오큰수이면 A와 B사이의 수 중에서 B가 가장 큰 수인 것을 이용한다. - 스..