[백준 / Python] 17298번 오큰수

문제 

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

 

 

소스코드

from collections import deque

N = int(input())
ls = list(map(int, input().split()))

deque = deque()
answer = [-1] * N

deque.append(0)
for i in range(1, N): # 
    while deque and ls[deque[-1]] < ls[i]:
        a = deque.pop()
        answer[a] = ls[i]
    deque.append(i)

print(*answer)

 

이 문제에서는 스택을 사용한다. 

소스코드에서 스택에 넣어지는 데이터는 값이 아니라 index이라는 것에 주의한다. 

 

스택에 먼저 0을 삽입한다. 

1부터 n-1까지 순회를 돈다. ( i in range(1, n) )  

- 여기서 ls[i] 를 스택의 꼭대기의 오큰수인지 판단할 것이다. 

- 만약 스택의 꼭대기보다 순회를 도는 데이터(ls[i])가 크다면 스택의 꼭대기 요소는 ls[i]가 오큰수이다. 

- 스택의 꼭대기를 제거하고 다시 ls[i]가 스택의 꼭대기 요소의 오큰수인지 판단한다. 

- 스택에 i인덱스의 오큰수를 찾기위해 i를 삽입하고 다음 순회를 진행한다.

 

여기서 스택 내에 있는 인덱스들은 오큰수를 찾기 위해 들어있다고 하면 이해가 편하다.