[Python] Baekjoon 2493. 탑

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

문제

풀이

import sys

input = sys.stdin.readline

n = int(input())
pillars = list(map(int, input().split()))[::-1]
stack = []
result = [0 for _ in range(n)]

stack.append(0)

for index in range(1, n):
    pillar = pillars[index]
    while stack and pillars[stack[-1]] <= pillar:
        result[(n - 1) - stack.pop()] = n - index
    stack.append(index)

print(' '.join(map(str, result)))

스택을 사용하여 풀 수 있었다.

탑에서 왼쪽으로 발사한 레이저는 자신과 높이가 같거나 더 높은 탑에 막힌다.
입력은 왼쪽 탑의 높이부터 들어오는데, 우리는 오른쪽 탑부터 왼쪽으로 이동하며 탑의 높이들을 비교해줘야 하기 때문에 입력 받은 값들로 생성한 pillars 리스트를 리스트 슬라이싱([::-1])을 통해 역순으로 뒤집어줬다.

stack에는 탑의 높이가 아닌 탑의 인덱스(index)가 삽입된다.
그 이유는 탑의 높이는 인덱스로 접근하여 알 수 있고 result에 삽입되어야하는 값은 결국 수신한 탑이 몇번째인지이므로 인덱스를 사용하는 것이 수월했기 때문이다.

가장 오른쪽에 위치한 탑부터 stack에 삽입한 뒤, 왼쪽의 탑으로 이동하며 만약 해당 탑의 높이가 stack에 가장 마지막으로 push된 값보다 크거나 같다면, 이를 pop한다.
stack에 삽입된 값은 결국 인덱스이므로, result에는 해당 인덱스에 수신한 탑의 위치를 삽입할 수 있도록 적절히 코드를 작성했다.

이 과정은 stack이 비어있지 않으면서 pillar의 값이 stack[-1]보다 크거나 같은 동안 반복되도록 코드를 작성했는데, 그 이유는 1개의 탑에서 수신할 수 있는 레이저가 다수일 수 있기 때문이다.

느낀 점

이 문제를 풀기 전 오큰수 문제를 풀어봤어서 그런지 풀이 방식을 생각하는 데 있어서 큰 어려움은 없었다.
유사한 접근 방식으로 새로운 문제를 풀어볼 수 있었음에 의미를 두고 싶다.