[골드 4] 백준 17298 - 오큰수 (파이썬)

'

https://www.acmicpc.net/problem/17298

풀이

주어진 수열에서, 각 원소에 대해 오른쪽에 있으면서 자기보다 큰 수 중 가장 왼쪽에 있는 수를 말한다. 없으면 -1을 출력한다.

for i in range(N - 1, -1, -1): 
    while len(stack) > 0 and stack[-1] <= A[i]:
        stack.pop(-1)

    stack.append(A[i])

    if len(stack) > 1:
        answer[i] = stack[-2]

stack에는 값이 저장되고 있고, 그것을 기반으로 stack[-2]를 사용하고 있는데, 이는 오큰수를 정확히 보장하지 않는다. 왜냐하면 stack[-2]는 항상 stack[-1] 보다 작거나 같다는 보장이 없고, 해당 원소 A[i]보다 큰 가장 가까운 오른쪽 값이 아닐 수도 있다.

예를 들어 A = [2, 1, 3] 일때 동작을 살펴보면 정확히 알 수 있다.

따라서, 주어진 코드는 스택에 값 자체를 넣고, 오큰수를 찾는 방식이 불안정하다.

코드

# 백준 17298 - 오큰수
# 분류 : 스택

N = int(input())
A = list(map(int, input().split()))

answer = [-1] * N
stack = []

for i in range(N - 1, -1, -1) :
    while len(stack) > 0 and stack[-1] <= A[i] :
        stack.pop(-1)
    
    stack.append(A[i])

    if len(stack) > 1 :
        answer[i] = stack[-2]

print(*answer)