[백준] 17298번 오큰수 (파이썬)

난이도 : GOLD IV

문제링크 : https://www.acmicpc.net/problem/17298

문제해결 아이디어

• 스택을 활용해서 접근했다.
• 스택에는 점점 작은 수가 쌓여야한다. => 현재 인덱스의 수와 스택의 마지막 인덱스와 비교해서 현재 인덱스가 더 큰 경우 해당 스택을 pop 하고 현재 인덱스값을 기록(오큰수)
  • 마지막인덱스보다 작을때 까지 반복한후 스택에 값 추가
• 아니면 그냥 스택에 값을 추가한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())

arr = list(map(int, input().split()))
stack = [[0, arr[0]]]
ans = [0] * n

for i in range(1,n):
    while stack:
        if stack[-1][1] < arr[i]:
           ans[stack.pop()[0]] = arr[i]
        else:
            break

    stack.append((i, arr[i]))

for idx, val in stack: # 남은 스택 정리 (오큰수가 없으므로)
    ans[idx] = -1

print(*ans)

여담

다른분들의 풀이를 보니 값은 필요없고 인덱스만 기록하면 되는거 였다.
그리고 ans의 기본값을 -1로 지정하면 남은 스택을 -1로 바꾸는 과정을 생략해도 된다.