[백준] 17298번 - 오큰수

---

문제 분석

N의 최대 크키가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과한다. 따라서 스택에 다음과 같은 아이디어를 추가해 이 문제를 풀어보면 된다.

1. 입력으로 주어진 수열과 스택의 top을 비교하는 과정을 진행한다.
2. 입력으로 주어진 수열이 스택의 top보다 크거나 같은 경우 pop하는 과정을 진행한다.
3. 스택이 비어 있게 되는 경우 -1 을 결과로 낸다

소스 코드

# 오큰수 구하기
import sys
input = sys.stdin.readline

N = int(input())
numList = list(map(int, input().split()))
stk = []
Result = []

for i in range(N-1, -1, -1):
    while stk and numList[i] >= stk[-1]:
        stk.pop()

    if len(stk) == 0:
        Result.append(-1)
    else:
        Result.append(stk[-1])

    stk.append(numList[i])

for value in Result[::-1]:
    print(value, end=' ')

해당 문제는 스택의 후입선출이라는 성질을 이용한 것으로 문제의 조건을 쉽게 해결한 것을 확인 할 수 있다.