[백준 알고리즘] 2493번: 탑 (Python / 파이썬)

 

문제 접근

간단히 생각해보면 오른쪽 -> 왼쪽으로 레이저를 쏴주므로

탑 리스트를 역순회하면서 오른쪽보다 큰 값인지 확인해야 한다.

 

6->5->4->7 과 같이 순회하는 경우

6,5,4 높이의 탑은 모두 7에서 수신한다. 따라 아직 수신되지 못한 신호를 보낸 탑들을 저장해 두어야 하는데

스택이 적합하다.

 

하나의 탑을 체크할때마다 스택의 top을 계속 확인하면 될것 같다.

스택이 비지 않았다면 top에 쌓여있는 걸 현재 탑의 높이와 비교하면서, 현재탑보다 낮은 것이 쌓여있다면 그것들은 다 pop하고 정답 배열에 추가하거나 바로 출력하면 된다.

위 작업을 하고 나서 스택에 현재 탑을 넣어준다.

 

중요한 부분은,

스택에 쌓여 있는 탑들과 현재 탑을 비교하고, pop하는 거까지는 문제가 없어도

그 스택에 쌓인 탑들이 어느 위치에 있었는지를 기억해야 한다는 것인데,

스택에 [ 탑 높이, 위치(인덱스) ] 형태 배열로 넣어줘서 해결했다.

pop하고 해당 정보를 기반으로 답안을 만들면 된다.

 

정답 코드

#2493번: 탑

import sys

n = int(sys.stdin.readline())
top_list = list(map(int, sys.stdin.readline().split(" ")))
stack = [] #아직 닿지 못한 레이저 리스트..
answer = [0 for i in range(n)]

for i in range(n):
    height = top_list[n-1-i]
    if len(stack) > 0:
        while stack:
            stack_top = stack[len(stack) - 1]
            if height >= stack_top[0]:
                answer[stack.pop()[1]] = n - i
            else: #수신할 수 없는 경우 중지
                break
    stack.append([height, n-1-i])

result_string = " ".join(map(str, answer))
print(result_string, " ")

 

 

 

---

2493번: 탑