백준 11279. 최대 힙

백준 11279번 최대 힙 문제

TRYS AND INSIGHTS

• python에서 우선순위 큐/힙을 담당하는 라이브러리는 heapq와 queue의 PriorityQueue가 있는데, 여기서는 heapq를 사용해서 풀었다.
• heapq
  • PriorityQue랑 달리 별개의 자료구조가 아님.
  • heapq 모듈의 함수를 호출할 때마다 리스트를 인자로 넘김
  • heappush, heappop: $O(logn)$
  • heapify(<list>): $O(n)$

	# 예시
        heap = []
        # 삽입
        heapq.heappush(heap, 1)
        heapq.heappush(heap, 2)
        # 삭제
        x = heapq.heappop(heap)
        print(x)

• sys.stdin.readline(): input() 대신 쓸 수 있음. python에서 입력받을 때 sys.stdin.readline은 필수인 것 같기도 함(이거 해야 시간 초과 에러 안 뜸)

[1번 시도]

sys.stdin.readline()을 안 써서 시간초과 뜸.

[2번 시도]

PriorityQueue를 썼더니 런타임에러 뜸.

원인: import queue나 PriorityQueue가 안 먹히는 것 같다는 추측성 글이 있음.

SOLUTION

최소 힙이 메인인 heapq에서 어떻게 해야 최대 힙으로 활용할 수 있을 지 고민하면서 구글링하다가 -1을 곱해서 넣으면 최소 힙으로도 최대힙처럼 사용할 수 있다는 것을 깨달음.
즉, 1<2<3<4의 각 요소에 -1을 곱해 주면 -1>-2>-3>-4가 되는 것처럼 최소 힙에 각 요소에 -1을 곱한 것을 넣어주고, 뽑을 때 원상복귀(-1 또 곱하기)해 주면 최대 힙처럼 쓸 수 있다는 것을 알 수 있음!

import heapq
import sys

def main():
    N = int(input())
    q = []; ans = []
    for _ in range(N):
        x = int(sys.stdin.readline())
        if x == 0:
            # 큐에서 rootpop하고 print
            if len(q) == 0:
                ans.append(0)
            else:
                ans.append(-1 * heapq.heappop(q))
        else:
            # 큐에 insert
            heapq.heappush(q, -1*x)

    for x in ans:
        print(x)

main()

여기서 온라인 알고리즘으로 구현했으면 더 좋았을 것 같기도 하지만, print()가 오래 걸린다는 걸 고려했을 때 그냥 이렇게 하는 게 좋을 것 같기도 함. 메모리에 큰 문제만 없다면..

자매품: 최소 힙

백준 1927. 최소 힙

최대 힙과 똑같이 풀되, -1 곱하는 부분만 빼면 됨.