[백준 - Python] 17298. 오큰수

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

 

코드

from collections import deque
import sys
input = sys.stdin.readline

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

ans = [-1] * n
stack = deque()

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

print(*ans)

 

접근 방법

- 문제 자체는 단순하고 쉬워보이지만, 수열의 크기가 최대 백만일 수 있기 때문에 시간 복잡도를 고려해야 한다

- 현재 값을 기준으로 더 큰 값을 '효율적으로' 찾을 방법이 필요하다

- 순차적으로 배열을 처리하면서, 특정 조건을 만족하는 경우 값을 처리하는 자료구조로 "스택"을 떠올릴 수 있어야 한다

- 오른쪽에 있는 큰 수 중에서 가장 왼쪽 수를 구하는 것이기 떄문에 위의 조건을 만족하고, 스택 자료구조를 활용할 수 있다

 

배운 점

- 스택 자료구조가 활용될 수 있는 경우에 대해 알 수 있었다