[BOJ] 17298

문제...
fail log

me

N=int(input())
A=deque(map(int,input().split()))
recents=deque([A.pop()])
res=deque([-1])
while A:
    rear=A.pop()
    found=False
    for recent in recents:
        if rear < recent:
            res.appendleft(recent)
            found=True
            break
    if not found : res.appendleft(-1)
    if len(A)!=0 and A[-1]< rear:
            recents.appendleft(rear)
print(*res)

지금보니깐 스택을 이용한 것 같진 않다.
38퍼에서 시간 초과 나던걸 45퍼에서 시간초과 나는 정도로 바꾼게 다이다.

solution

import sys
n = int(input())
A = list(map(int, sys.stdin.readline().split()))
answer = [-1] * n
stack = []


stack.append(0) # 첫 번째 index
for i in range(1, n): # 비교
    while stack and A[stack[-1]] < A[i]: # while 대신 if는 안되나?
        answer[stack.pop()] = A[i] # 해당 자리에 오큰수 넣기
    stack.append(i)


print(*answer)

그래서 stack을 이용하여 문제를 풀었다.
stack에는 원소값이 아닌 원소의 인덱스를 넣어주는 목적으로 사용하였다.

예를 들어, 3 5 2 7 이라는 수열이 있을 때
처음 스택에는 0이 들어가 있으며, A[1]과 A[stack[-1]의 원소를 비교한다.
stack[-1]은 0이기 때문에 A[1]과 A[0]을 비교하는 것이며, A[1]의 값이 더 크므로
answer[0]에는 A[1]의 값인 5를 넣어주게 되는 것이다. 즉 0의 오큰수를 구한 것이다.
그리고 0인덱스는 오큰수를 구했기 때문에 pop을 하고, 다음으로 구해야 할 인덱스 1을 넣어주는 것이다.

만약, 현재 i가 오큰수를 구하지 못했다고 하더라도 stack에 현재 인덱스i를 추가해야 한다.
그래야 이어서 i+1의 오큰수를 구할 수 있고, i+1의 오큰수를 구하면 자동으로 i의 오큰수도 구하게 되기 때문이다

참고