백준 17298번 오큰수

문제 풀이

• stack을 이용해서 시간복잡도를 줄여야 문제를 해결할 수 있습니다.

• 주어진 수열을 1번 인덱스부터 끝까지 순서대로 조회합니다
  (for i in range(1, n)).

• stack에는 조회한 인덱스가 차례대로 쌓입니다
  (stack.append(i)).

• 만약 현재 조회하고 있는 수(sequence[i])가 스택의 마지막 인덱스(마지막 수: stack[-1])와 맵핑되는 수(sequence[stack[-1]])보다 크다면, 맵핑되는 수의 오큰수는 현재 조회하고 있는 수가 됩니다.(result[stack.pop()] = sequence[i])

  • 이때 스택을 마지막부터 거슬러 내려가면서 현재 조회하고 있는 수가 스택의 마지막 인덱스가 오큰수인지 판별하고 오큰수가 아닐 때까지 거슬러 내려갑니다
    (while stack and sequence[stack[-1]] < sequence[i]).

코드 풀이

import sys
input = sys.stdin.readline

n = int(input())
sequence = list(map(int, input().split()))
result = [-1] * n
stack = [0]
for i in range(1, n):
    while stack and sequence[stack[-1]] < sequence[i]:
        result[stack.pop()] = sequence[i]

    stack.append(i)

print(*result)

예시

# 주어진 수열
- sequence = [3, 5, 2, 7]

# 초기값
- result = [-1, -1, -1, -1]
- stack = [0]

# i = 1
- sequence[0] < sequence[1] : True
	
    - result[0] = sequence[1]
    - result = [5, -1, -1, -1]
    - stack = []
    
- stack = [1]

# i = 2
- sequence[1] < sequence[2] : False
- stack = [1, 2]

# i = 3
- sequence[2] < sequence[3] : True

	- result[2] = sequence[3]
    - result = [5, -1, 7, -1]
    - stack = [1]

- sequence[1] < sequence[3] : True

	- result[1] = sequence[3]
    - result = [5, 7, 7, -1]
    - stack = []

- stack = [3]