CodeDrive

문제:

크기가 N인 수열 A=A1,A2,...,AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3,5,2,7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력:

첫째 줄에 수열 A의 크기 N (1<=N<=1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1,A2,...,AN(1<=Ai<=1,000,000)이 주어진다.

출력:

총 N개의 수 NGE(1), NGE(2),... ,NGE(N)을 공백으로 구분해 출력한다.

풀이방법:

for를 두 번 사용해서 문제를 풀 수 있지만 O(n^2) 시간복잡도로 인해서 시간초과가 발생한다. 따라서 효율적인 방법인 스택을 사용해야 한다.

이와 비슷한 문제들은 수열의 값들을 저장하면서 진행을 하지만, 이 문제는 독특하게 인덱스를 저장하면서 진행한다.

조건에 맞는 오큰수가 없다면 -1을 넣어주어야 하므로, 애초에 크기가 len(A)이고, 값이 -1인 answer 배열을 만들어 준다.

이후에는 배열을 한번 순회할 때, idx의 마지막(top)에 해당하는 값과 반복문의 인덱스값과 비교하고, 이 때, 반복문의 인덱스값이 크다면 idx의 top에 해당하는 값을 인덱스로 해서 answer의 값(answer[idx.pop()])을 반복문의 인덱스(i) 값(A[i])으로 바꿔주도록 한다. 그리고 이는 while로 반복된다.

while이 끝나면 지금 반복문 인덱스를 idx에 넣어준다.

www.acmicpc.net/problem/17298