BAEKJOON #17298 오큰수

이 문제의 저작권은 BAEKJOON에 있습니다.

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

 

풀이

1. n크기 만큼의 -1 리스트를 생성
2. for문으로 n만큼 반복
   1. stack이 존재하고 arr[stack[-1]] < arr[i] 일때 while문 실행
      1. stack의 마지막 요소를 pop하고 answer인덱스로 사용, arr[i]값을 삽입
   2. stack에 현재 i값(인덱스)를 삽입

# 오큰수
# https://www.acmicpc.net/problem/17298

from collections import deque

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

# 미리 -1 리스트 생성
answer = [-1 for i in range(n)]

for i in range(n):
    # stack이 존재하고 stack의 맨 마지막 값을 index로 하는
    # arr보다 arr[i]가 크다면 조건 성립
    while stack and arr[stack[-1]] < arr[i]:
        # answer[stack.pop()] 으로 stack값을 pop하며
        # 해당 index에 arr[i]값을 삽입
        answer[stack.pop()] = arr[i]
    # stack에는 index값을 삽입한다.
    stack.append(i)
print(*answer)