[백준] 17298 오큰수 (Python)

풀이 과정

처음에는 A 리스트에서 A[i+1] < A[N] 일 때를 발견한 후 flag 로 표시한 후 답 리스트에 추가해줘야겠다고 생각했다. 그러면 전체 for 문과 i 일 때의 for 문 두 개로 나뉘므로 시간 초과로 고생하는 (동방에 있던 사람 피셜...) 문제라 분명 오답일 것 같았다. 수열 배열을 생각하다가 옛날에 카운팅 정렬에 대해 알아보았던 게 기억났다. 

제가 풀엇어요

result[stack.pop()] = A[i] 대신 result.append(A[i]) 를 했다가 혼쭐났다. 바본가 result.append 는 result 맨 끝에 수를 추가하는 것이다. stack 에 저장한 해당 index 의 오큰수를 result 같은 index 에 저장해야 하기 때문에 result[stack.pop()] = A[i] 를 사용해서 추가해줘야 한다.

import sys
input = sys.stdin.readline

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

result = [-1] * n
stack = []

stack.append(0)

for i in range(1, n):
    while stack and A[stack[-1]] < A[i]:
        result[stack.pop()] = A[i]
    stack.append(i)

print(*result)