백준 2493 <탑> Python

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

---

스택의 성질을 이용해 풀 수 있는 문제입니다.

 

임의의 위치에서 탑이 신호를 쏘았을 때 신호를 받는 탑은 [높이가 신호를 쏜 탑의 높이 이상이고, 신호를 쏜 탑보다 왼쪽에 위치한] 탑입니다. 그러므로 해당 조건 중 하나라도 해당하지 않는다면 문제를 푸는 데 필요가 없습니다. 즉 왼쪽에 위치한 탑 부터 하나씩 추가하고 추가될 탑의 바로 왼쪽에 있는 탑 == 가장 마지막에 추가된 탑부터 조건에 맞는지 확인하며 하나씩 제거해도 문제를 푸는데 지장이 없습니다.

 

점차적으로 비교 대상을 줄여가며 주어진 시간과 메모리 내에서 문제를 해결할 수 있게 됩니다.

---

import sys

input = sys.stdin.readline


def solution(N, heights):
    # 수신탑 목록
    receive_list = [0]
    # 스택
    stack = [[0, heights[0]]]
    # 높이의 왼쪽부터 하나씩 추가
    for idx in range(1, len(heights)):
        # 현재 높이
        now_height = heights[idx]
        # 추가될 높이가 직전 높이보다 높으면 직전 높이는 소용 없음
        # 앞선 높이가 현재 높이보다 낮으면 모두 팝
        while stack and stack[-1][1] <= now_height:
            # 팝
            stack.pop()
        
        # 남은 탑이 없으면 0
        if not stack:
            receive_list.append(0)
        
        # 남은 탑이 있으면 마지막 탑 인덱스
        else:
            receive_list.append(stack[-1][0]+1)

        # 현재 높이 추가
        stack.append([idx, now_height])

    print(*receive_list)


# 입력
N = int(input().strip())
heights = list(map(int, input().strip().split()))

solution(N, heights)