[Baekjoon] 2493. 탑

🔗 Problem Link

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

---

❔Thinking

• 탑의 높이가 주어진 배열에서, 현 위치 왼쪽에 위치한 높은 탑의 가장 가까운 위치를 담아 반환한다.
• 동일한 높이의 탑도 포함하여 확인한다.
• 결국, 자신보다 높지 않은 탑은 비교 대상에서 제외된다.

---

💻Solution

import sys
input = sys.stdin.readline

N = int(input().rstrip())
buildings = list(map(int, input().split()))
laser = [0] * N
stack = [(0,0)] # (위치, 높이)
for idx, height in enumerate(buildings):
    while stack and stack[-1][1] < height:
        stack.pop()
    if stack:
        laser[idx] = stack[-1][0]+1
    stack.append((idx, height))
print(' '.join(map(str,laser)))

---

🗝️keypoint

1. 왼쪽으로 가면서 자신보다 높은 탑이 나오면 해당 위치를 담는다.
2. 모든 탑에 대해 자신보다 높은 탑의 위치를 확인하기 때문에, 자신의 높이보다 탑은 stack에서 제거할 수 있다.
   1. 만약 [8, 1, 2, 3, 4, 5]로 탑이 주어진다면, 사실상 stack에는 (0, 8)만 계속 남아있게 된다.
   2. [8, 1, 2, 5, 4]로 탑이 주어진다면, 4의 경우 [(0,8), (3,5)]인 stack에서 5인 탑과 비교하게 된다.