17298 오큰수 - python

N=int(input())
a=list(map(int, input().split()))
ans=[-1 for _ in range(N)]
#오큰수를 찾지 못한 애들의 인덱스를 스택에 저장
stack=[]
for i in range(len(a)):
    if len(stack) == 0:
        stack.append(i)
        continue
    else:
        while True:
            if a[stack[-1]] < a[i]:
                ans[stack[-1]] = a[i]
                stack.pop()
                if len(stack) == 0:
                    stack.append(i)
                    break
                else:
                    continue
            else:
                stack.append(i)
                break

ans=list(map(str, ans))
print(' '.join(ans))

오큰수가 없는 애들의 답은 -1이기 때문에, 처음에 전부 -1을 답으로 한 리스트를 만들어주었습니다.

이후 오큰수를 찾지 못한 애들의 인덱스를 스택에 저장하였습니다.

값이 아닌 인덱스 값을 저장하는 이유는 -1이었던 정답을 업데이트 해야 할 때 위치가 필요하기 때문입니다.

그리고 스택에 저장되는 인덱스들의 실제 값은 내림차순으로 저장될 것입니다.

예를 들어, stack = [1, 2, 3, 4]라고 한다면 a[1] > a[2] > a[3] > a[4]가 되는 것입니다.

이후 a[5]와 a[1], a[2], a[3], a[4]를 비교할 때, a[4] = a[stack[-1]]부터 비교하되 만약 a[5]가 a[4]보다 작다면 stack에 5를 추가한 뒤, a[3], a[2], a[1]은 비교하지 않고 다음으로 넘어가면 됩니다.