[백준 17298번-파이썬]오큰수

백준 (BOJ) 17298번
https://www.acmicpc.net/problem/17298

사용언어 : PYTHON

1.문제

2.풀이

시간제한이 1초이기 때문에 중첩 반복문으로 풀게되면 시간초과가 나올것 같아서 스택을 사용하여 풀어야겠다고 생각했다.
처음에는 큰 수에 생각이 사로 잡혀서 스택에 가장 큰 값을 유지하면 안될까? 라는 생각을 계속하였다. 1시간 정도 고민해보다 도저히 안될것 같아서 다른분들의 풀이를 검색하였다.
검색을 통해 알게된 아이디어는 다음과 같다.
스택에 수열의 가장 큰 값을 유지하는 것이 아닌, 스택의 제일 윗 값보다 큰 값이 나올때 까지 수열의 값들을 차례대로 쌓는 것이었다. 그러다가 스택의 제일 위의 값보다 큰 수열의 값이 나오면 그 수는 스택 제일 윗 값의 오큰수가 된다. 이 동작을 pop하면서 스택의 제일 윗값보다 작을때 까지 반복하면 된다.

그림으로 나타내면 다음과 같다
처음에는 스택에 아무것도 없으므로 3을 넣는다
스택 가장 위의 값 3보다 작으므로 2도 append한다
스택의 가장 윗 값 2보다 4가 크므로 4가 2의 오큰수이다. 2를 pop하고, 스택의 가장 윗 값은 3이되는데 3보다 4가 크므로 3의 오큰수도 4가 된다.
그리고 더이상 비교할 수가 없으므로 4를 append한다.

1은 4보다 작으므로 append한다.
8은 1보다 크므로 1의 오큰수가 된다. 1을 pop하면 4가 스택의 가장 윗 값이되는데 4보다 8이 크므로 4의 오큰수도 8이 된다.

이때 answer배열의 적절한 위치에 오큰수를 넣어야 하는데, 이를 위해선 스택에 배열의 값만 넣는것이 아닌, 인덱스를 같이 넣어줘야 한다.

3.코드

import sys

input = sys.stdin.readline

N=int(input())
a=list(map(int,input().split()))
answer=[-1]*N
stck=[]

for i in range(N):
    while len(stck)>0 and stck[-1][0] < a[i]:
        val,idx=stck.pop()
        answer[idx]=a[i]
    
    stck.append([a[i],i])

print(*answer)