[백준] 17298 - 오큰수 (Python)

문제

크기가 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)을 공백으로 구분해 출력한다.

아이디어

하나씩 확인하게되면 시간초과가 발생하기 때문에 같은 오큰수를 가진 수는 다시 확인할 필요없이 같은 오큰수 값을 저장하는 것이다.

풀이

문제만 보고 단순히 코드를 짜게되면 이중포문을 돌려 하나씩 전부다 확인하는 방법으로 O(n^2)으로 풀 수 있다. 하지만 당연히 시간초과가 발생해 다른 방법이 필요하다. 숫자를 담을 스택을 하나 준비한다. 이 스택에 입력으로 주어진 숫자 리스트를 하나씩 넣는데 만약에 리스트에서 뽑은 숫자가 스택의 마지막 숫자보다 크면 오큰수이기 때문에 pop을 하여 정답에 저장한다. 이 과정을 스택에 오큰수가 아닌 값이 나올 때까지 반복한다. 

코드

def solution():
    n = int(input())
    nums = list(map(int, input().split()))
    answer = [-1]*n
    rest = []
    
    for i in range(n):
        while rest and nums[i]>rest[-1][1]:
            answer[rest.pop()[0]] = nums[i]
            
        rest.append((i, nums[i]))

    print(*answer)

if __name__=="__main__":
    solution()