[백준] 2493번 탑 - 파이썬(Python)

문제 (링크)

 

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

2493번: 탑

 

나의 풀이

import sys
input = sys.stdin.readline

n = int(input())
tops = list(map(int, input().split()))

stack = []
# 인덱스와 탑의 높이
stack.append([1, tops[0]])
# 맨 왼쪽 탑은 수신되지 않음
ans = [0]

for i in range(1, n):
    while stack:
        if stack[-1][1] >= tops[i]:
            ans.append(stack[-1][0])
            stack.append([i + 1, tops[i]])
            break
        
        else:
            stack.pop()

    if not stack:
        ans.append(0)
        stack.append([i + 1, tops[i]])

print(*ans, end=" ")

 

코드 설명 및 풀이법

탑의 인덱스와 높이를 묶은 후, 스택을 통해 문제를 해결했다.

 

탑의 신호는 자신보다 크거나 같은 높이의 탑 중 가장 가까운 탑에 수신되기 때문에,

 

만약 특정 탑이 그것의 왼쪽 탑보다 높이가 높다면 그 탑의 오른쪽에 있는 탑은 왼쪽 탑에게 신호를 줄 수 없다.

 

따라서, 만약 현재 탑의 높이보다 스택의 top에 있는 탑의 높이가 더 작다면 해당 탑은 pop을 해줘도 무방하다.

 

이 원리를 이해하면 크게 어렵지 않은 문제이다.