[17298] 오큰수 (스택)

17298번: 오큰수

 

분석

• 스택에 새로 들어오는 수 > top에 존재하는 수 : 새 수는 오큰수, top pop하면서 새 수 push
• 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1 출력
• 순서
  1. 스택이 채워져 있거나 a[idx] > a[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장.
     • pop은 조건을 만족하는 동안 계속 반복
  2. 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어감
  3. 수열의 길이만큼 반복하고 스택에 남아있는 인덱스에 -1 저장

 

풀이

import sys
n = int(input())
a = list(map(int, input().split()))
stack = []
res = [0]*n # 정답리스트

for i in range(n):
    while stack and a[stack[-1]] < a[i]: # 스택 탑 인덱스가 가르키는 수 < 현재 수
        res[stack.pop()] = a[i] # 정답 리스트에 오큰수를 현재 수로 저장
    stack.append(i)

while stack: # 반복문을 다 돌고 나왔는데 스택이 비어 있지 않다면 빌 때까지
    res[stack.pop()]=-1 #스택에 쌓인 index에 -1을 넣기

for i in range(n):
    sys.stdout.write(str(res[i]) + " ")