[BOJ] 백준 17298 오큰수 Python

17298번: 오큰수

문제풀이
스택을 이용해서 풀었다.
N의 최대값이 1,000,000이기 때문에 O(N^2)으로는 절대 풀 수 없었기에 배열을 순회하는 것은 불가능하다고 생각했다.
그래서 오큰수 배열인 NGE배열을 [-1]로 N의 크기만큼 초기화 시켜놓은 후, 어차피 NGE배열의 크기와 입력받은 배열의 크기가 같기때문에 값의 비교를 통해 값과 인덱스를 스택에 저장시켜 NGE배열에 넣어주는 과정을 거쳤다.
1. N과 arr을 입력받고 NGE배열을 -1로 N의 크기만큼 초기화시키고 stack을 빈 리스트로 선언한다.
2. arr의 모든 배열값을 한번은 반드시 순회해야하기에 i로 for문으로 돌며 스택에  [값,인덱스]형식으로 추가한다.
2-1. 이 때 스택에 값이 존재하고 스택의 상단(top)이 현재 arr[i]값보다 작으면 오큰수가 바뀌어야하기에 스택에서 값과 인덱스를 pop한후 NGE배열의 pop된 인덱스에 arr[i]값을 넣어주며 오큰수배열(NGE)를 최신화 시킨다.

Code

from sys import stdin

input = stdin.readline


def solve():
    N = int(input())
    arr = list(map(int, input().split()))
    stack = []
    NGE = [-1] * N
    for i in range(N):
        while stack and stack[-1][0] < arr[i]:
            num, idx = stack.pop()
            NGE[idx] = arr[i]
        stack.append([arr[i], i])
    print(*NGE)


solve()