백준 - 탑 / Gold 5 / 2493번 / Python

문제 📋

백준 - 탑

풀이 📝

import sys


class Tower:
    def __init__(self, num, height):
        self.num = num
        self.height = height


def solution(n, towers):
    answers = [0] * n
    stack = []

    for i in range(n):
        towers[i] = Tower(i+1, towers[i])

    stack.append(towers[-1])

    for i in range(n-2, -1, -1):
        while stack and stack[-1].height < towers[i].height:
            tower = stack.pop()
            answers[tower.num - 1] = i+1

        stack.append(towers[i])
    return answers


n = int(sys.stdin.readline())
towers = list(map(int, sys.stdin.readline().split()))

answers = solution(n, towers)

for answer in answers:
    print(answer, end=" ")

탑들을 역순회하면서 레이저를 송신하는 탑이 나타날 때까지
자료구조에 저장하여 관리해야 한다.

그럼 어떠한 자료구조가 적합할까?

바로 스택이다.
왜냐하면 스택에 들어왔다는 건 현재 스택에 있는 탑보다 높이가 낮다는 것이다.
그렇기 때문에 최근에 들어온 데이터(탑)부터 높이를 대조하여 처리해야 누락되는 데이터가 없을 것이다.

그래서 LIFO(Last In First Out)인 스택을 선택했다.