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

Ed Park·2023년 4월 7일
0

문제 📋

백준 - 탑


풀이 📝

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)인 스택을 선택했다.

profile
Simple is the best

0개의 댓글