[백준] 17298 오큰수 python

www.acmicpc.net/problem/17298

17298번: 오큰수

n = int(input())
numbers = list(map(int, input().split()))
answer = [-1] * n
val = 0
stack = []
for i in range(n - 2, -1, -1):
    tmp = numbers.pop()
    stack.append(tmp)
    if numbers[i] < tmp:
        val = tmp
    if numbers[i] >= val:
        while stack:
            val = stack.pop()
            if numbers[i] < val:
                answer[i] = val
                stack.append(val)
                break
    else:
        answer[i] = val

print(*answer)

스택의 개념을 사용한 문제이다.

쉬운 문제인줄 알고 덤볐으나 반례찾기 너무 어려워서 포기할뻔했다

배열의 크기와 같은 정답의 배열을 -1로 초기화시키고, 배열의 뒷부분부터 앞으로 순회하며 비교한다.

오른쪽 값이 크면 해당값을 stack에 push하고, 왼쪽값이  크면 stack에서 큰값이 나올때까지 pop한다.

왼쪽값이 큰경우에서 반목문을 돌려 오른쪽 값이 큰값이 나온경우 그 값을 다시 stack에 push하고 나오지 않은경우 값이 -1로 초기화되어있기 때문에 넘어간다.