Skip to content

2493. 탑

TLDR#

stack으로 문제를 푼다. 모든 탑이 서로 왼쪽방향으로 레이저를 쏘기 때문에, while 문을 돌면서 새 탑의 높이보다 낮은 탑들을 스택에서 지워나가야 한다. 이때 스택의 순서대로 지워나가야 한다.

Snippet#

"""
http://boj.kr/2493
"""

from collections.abc import Generator, Iterable
from sys import stdin


def input():
    return stdin.readline().strip()


type height = int
type index = int


def main(seq: Iterable[height]) -> Generator[index | None, None, None]:
    """
    seq: 각 원소는 탑의 높이를 의미, 순서대로 왼쪽서부터 오른쪽 방향으로 탑을 세운다.
    returns: 모든 탑에서 왼쪽 방향으로 레이저를 쏘았을 때 레이저를 수신하는 탑의 인덱스를 리턴하라. 만약 어떤 탑도 레이저를 수신할 수 없는 경우, None을 리턴한다.
    """
    yield None  # 제일 왼쪽의 레이저는 항상 수신탑이 존재하지 않는다.

    it = iter(seq)
    stack: list[tuple[height, index]] = [(next(it), 0)]

    for i, h in enumerate(it, start=1):
        # print(i, h, stack)
        while len(stack) > 0 and stack[-1][0] <= h:
            stack.pop()  # 새로 세울 탑보다 높이가 낮은 탑들은 앞으로 레이저를 수신할 수 없음.
        if len(stack) > 0:
            yield stack[-1][1]
        else:
            yield None

        stack.append((h, i))


if __name__ == "__main__":

    def result_to_output(result: index | None) -> int:
        if result is None:
            return 0
        return result + 1  # 1부터 세는 인덱싱

    n = int(input())

    print(" ".join(str(result_to_output(x)) for x in main(map(int, input().split()))))

Sample Input & Expected Output#

Input#

5
6 9 5 7 4

Expected Output#

0 0 2 2 4

Notes#

  • 마지막 줄 문제풀이를 위한 input().split() 결과를 main에 집어넣기 위해 map을 쓰고, 그 결과를 comprehension으로 다시 작성하고 그 결과를 result_to_output에 넣은 뒤 그 결과를 str으로 변환하여 " " 에 join 하는 이 작업이 굉장히 복잡하게 느껴진다. 사람이 읽는 순서대로가 아니라서 더 그렇게 느껴지는 것 같기도 하다. 파이썬에도 pipeline 연산자가 있어서 data $ func1 $ func2 $ func3 이런 식으로 체이닝 해 나갈 수 있게 할 수 있으면 좋을 것 같다.