[Python] 백준 2493 - 탑 문제 풀이

Overview

BOJ 2493번 탑 Python 문제 풀이
분류: Data Structure (자료구조)

---

문제 페이지

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

---

풀이 코드 1 - Stack

from sys import stdin


def main():
    n = int(stdin.readline())
    towers = list(map(int, stdin.readline().split()))

    stack = []
    res = [0] * n

    for i, tower in enumerate(towers):
        while stack and stack[-1][1] <= tower:
            stack.pop()

        if stack:
            res[i] = stack[-1][0]

        stack.append((i + 1, tower))

    print(*res, sep=' ')


if __name__ == "__main__":
    main()

탑을 순서대로 탐색하면서 답을 구한다.
스택에서 현재 탑의 높이보다 낮은 것들을 모두 꺼내면, 스택 맨 위에 있는 값이 수신 받는 탑이 된다. 만약 스택에 남아 있는 값이 없다면, 수신 받을 수 있는 탑이 없으므로 수신 위치는 0이 된다. 수신 위치를 구한 뒤에는 현재 탑 정보를 스택에 넣고 이전 과정을 반복한다.

위 코드는 탑들을 탐색하는 for문과 그 내무에 스택을 탐색하는 while문으로 인하여, O(N^2)의 시간 복잡도를 가진다

---

풀이 코드 2 - Heap

from sys import stdin
from heapq import heappop, heappush


def main():
    n = int(stdin.readline())
    towers = list(map(int, stdin.readline().split()))

    res = [0] * n
    hq = []
    for i in range(n - 1, -1, -1):
        while hq and hq[0][0] < towers[i]:
            t, idx = heappop(hq)
            res[idx] = i + 1

        heappush(hq, (towers[i], i))

    print(*res, sep=' ')


if __name__ == "__main__":
    main()

탑들을 오른쪽에서 왼쪽 방향으로 탐색하며 답을 구하는 방법이다.
힙에서 현재 탑의 높이보다 작은 값들을 모두 꺼내고, 각 탑들의 수신 위치를 현재 탑 위치로 설정한다. 그 다음 현재 탑의 정보도 힙에 넣고 이전 과정을 반복한다.

이 풀이는 O( N^2log(N) )의 시간 복잡도를 가지며, 첫 번째 풀이보다는 느리다.