[백준] 17298번 오큰수(python)

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

17298번: 오큰수

 

1. 난이도 골드 4

 

2. 문제 해결 방법

시간초과, 메모리초과 난사로 멸망당하고 구글링을 해서 풀었다.

 

answer이라는 배열을 -1로 모두 저장해놓은 후, 

 

stack에 값이 있고, num[index] > stack[top] 인 경우 인덱스를 이용해 정답 배열에 오큰수를 저장한다.

 

위의 과정이 끝나면

 

현재 인덱스를 스택에 저장하고 다음 인덱스로 넘어간다.

 

import sys

input = sys.stdin.readline

n = int(input().rstrip())

num = list(map(int, input().rstrip().split()))
answer = [-1] * n
stack = []

for i in range(n):

  while stack and num[stack[-1]] < num[i]:
    answer[stack.pop()] = num[i]
  
  stack.append(i)


for i in answer[:-1]:
  print(i, end=" ")

print(answer[-1])