문제 : https://www.acmicpc.net/problem/2493

문제

건물 높이들을 입력받은 후 뒤에서부터 레이저 신호를 보내고, 해당 레이저 신호가 몇번째 건물가지 도달하는지 체크하면 되는 문제이다. 문제 해석은 간단하니 자세한 설명은 생략한다.

풀이

greedy + stack

해당 건물에서 순차적으로 읽어올 때 가장 큰 건물의 위치만 알아내면 된다. 따라서 레이저를 최종적으로 수신하는 건물의 위치만 알아내면 되는 것이다. 그러면 해당 건물에서 0번째 건물까지 계속해서 탐색하면 되는것인가?
그렇게 하면 당연히 n * n 의 시간이 걸릴 것이므로 시간초과가 발생할 것이다. 따라서 효과적으로 가장 높은 건물의 위치만을 알아내는 방법이 필요하다. 이때 필요한 것이 바로 스택이다.

1. 스택에 아무것도 없을 때 해당 건물 쌓기
2. 있다면 스택의 top부분과 비교하며 pop하기(top이 작다면 pop)
   이때 pop한 개수만큼 해당 건물의 위치값을 최종 answer값에 저장하기
   (필자 코드에서는 answer 대신 outputs로 하였다)
3. 최종적으로 리스트를 str 형태로 print 출력하기

code

n = int(input())
heights = list(map(int,input().split()))
stack = []
outputs = [0 for _ in range(n)]

for i in range(len(heights)-1,-1,-1):
    h = heights[i]
    if not stack:
        stack.append((h,i))
        continue
    
    
    while stack and stack[-1][0]<h:
        _, idx = stack.pop()
        outputs[idx] = i+1
    stack.append((h,i))
    
print(' '.join(map(str,outputs)))

result

deque를 사용하여 풀 수 있지만, 필자는 list method인 pop과 append를 이용하여 해결하였다. 여기서 중요한 것은 pop()할 때 인자값을 안넣어주면 가장 마지막꺼를 remove한다는 것!!
(queue처럼 맨 앞에꺼 없어지는 걸로 착각해서 몇번 틀렸다..)