1️⃣ 서론
이 문제는 백준 2493 탑 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다.
2️⃣ 문제 설명
모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 만드는 문제이다.
3️⃣ 풀이
위의 그림을 보면 답이 [0, 0, 2, 4, 4]가 됨을 확인할 수 있다. 이를 오른쪽부터 살펴보았을 때 레이저가 자신의 탑 보다 큰 탑이 나와야지만 그 탑이 답이 됨을 알 수 있었는데 이를 스택을 써서 미리 들어와 있는 탑 중 현재 탑 보다 작은 탑은 전부 pop하여 현재 탑의 인덱스를 답으로 해놓으면 되겠다라는 생각을 하였다.
이를 구현한 코드는 다음과 같다.
4️⃣ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
stack = []
answer = [0] * n
idx = n
while len(arr) != 0:
k = arr.pop()
# 스택이 비어있으면 현재 탑을 스택에 넣음
if len(stack) == 0:
stack.append([k, idx])
else:
# 현재 탑보다 키가 작은 탑은 전부 현재 탑의 인덱스를 답으로 한다.
while True:
if len(stack) != 0 and stack[-1][0] <= k:
item, item_idx = stack.pop()
answer[item_idx - 1] = idx
# 더 이상 크기가 작은 탑이 없다면 스택에 현재 탑을 추가
else:
stack.append([k, idx])
break
idx -= 1
for x in answer:
print(x, end=" ")
5️⃣ 마치며
골드 5였지만 그렇게 어려운 문제는 아니었던 것 같다. 스택의 개념만 잘 생각한다면 쉽게 풀 수 있는 문제였다.
