BOJ 2493(탑) 풀이

이미지를 누르면 문제로 이동합니다

요약하면 i 번째 탑이 있으면 그 탑의 왼쪽에 있는 탑 중에서 i번째 탑의 높이보다 크거나 같은 높이를 가진 탑의 위치를 출력하고 없다면 0으로 출력하는 문제이다.

 

이 문제는 스택을 쓰면 되는 간단한 문제이다.

왼쪽부터 차례로 돌면서 스택에 있는 값들중 자신보다 작은 값들을 지워준다. 어차피 i+1 이후의 탑들 중 i번째 탑에 막힌다면 그전 탑에는 절대 도달할 수 없고, i 번째 탑보다 커도 그전 탑들은 i 번째 탑보다도 작기 때문에 쓸모가 없다. 그러므로 매 반복마다 i 번째의 탑보다 작은 높이의 탑들을 스택에서 빼주고 남은 스택의 첫 번째 탑의 위치를 구해주면 된다. 만약 스택에 들어있는 값이 없다면 0을 출력해 주면 된다.

 

import sys
from collections import deque
input=sys.stdin.readline
a=int(input())
l=list(map(int,input().split()))
st=deque([[l[0],1]])
ans=[0]
for i in range(1,a):
    while len(st)>0 and st[0][0]<l[i]:
        st.popleft()

    if len(st)==0:
        ans.append(0)
    else:

        ans.append(st[0][1])
    st.appendleft([l[i],i+1])
    

for i in range(len(ans)):
    print(ans[i],end=" ")