백준 17298[오큰수 구하기]

1. 문제분석 및 접근법

• 시간복잡도 때문에 매번 뒤에 있는 수를 비교하면 안됨.
• 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 오큰수임
• 마지막 숫자는 무조건 -1을 출력

1. 스택이 채워져 있고, 탑보다 새로 들어오는 숫자가 큰 경우 pop한 인덱스를 이용해 정답 수열에 오큰수를 저장
2. pop을 조건을 만족하는 동안 반복
3. 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어감
4. 반복 후 현재 스택에 남아 있는 인덱스에 -1 저장

2. 슈도코드

n 입력받기
a 입력받기(리스트)
ans 정답리스트 생성
myStack 스택 선언

for i -> n까지:
	while 스택이 비지 않고, 현재 수열값이 top에 해당하는 수열보다 클 때까지:
    	스택에서 pop한 값을 index로 하는 정답 리스트 부분을 수열 리스트의 현재 값(a[i])로 저장
    스택에 i값을 저장

while 스택이 빌 때까지:
	스택에 있는 index의 정답 리스트에 -1 저장

출력

3. 코드 구현

import sys
input = sys.stdin.readline

n = int(input())
ans = [0] * n
a = list(map(int, input().split()))
myStack = []

for i in range(n):
    while myStack and a[myStack[-1]] < a[i]:
        ans[myStack.pop()] = a[i]
    myStack.append(i)

while myStack:
    ans[myStack.pop()] = -1
    
result = ""
for i in range(n):
    sys.stdout.write(str(ans[i]) + " ")
    
print(result)