[백준/파이썬] 17298번

📍백준 17298번 문제

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

코드

# 풀이 1 - 시간초과
import sys
from collections import deque

input = sys.stdin.readline

num = int(input())

li = deque(list(map(int, input().split())))
nge = []

for i in range(num):
    flag = 0
    for i in range(len(li)):
        if li[0] < li[i]:
            nge.append(li[i])
            flag = 1
            li.popleft()
            break
    if flag == 0:
        nge.append(-1)
print(*nge, end="")

# 풀이 2
import sys
from collections import deque

input = sys.stdin.readline

num = int(input())

li = list(map(int, input().split()))

nge = [-1] * num

stack = deque()

for i in range(num):
    while stack and (stack[-1][0] < li[i]):
        temp, index = stack.pop()
        nge[index] = li[i]
    stack.append([li[i], i])
print(*nge)

풀이

• 풀이 2의 경우 stack을 이용해서 풀면 된다.
  오큰수를 아직 구하지 못한 경우, stack에 넣어준다.
  stack에 값을 저장할 때, 이중배열구조를 통해 인덱스와 값을 동시에 넣어준다.
  현재 값이 stack 마지막 값보다 클 경우, pop을 통해 stack에서 값을 제거한다. 이후에 nge 배열에 오큰수인 현재 배열의 값을 넣어주면 된다.