[BOJ] 1927 최소힙, 11279 최대힙 - Python

문제

---

1927번: 최소 힙

 

 

11279번: 최대 힙

 

풀이

---

위 두 문제는 python의 heapq 모듈을 사용하면 쉽게 풀 수 있는 문제입니다.

 

문제 제목에서도 풀이를 유추할 수 있었지만 입력으로 주어지는 최대 N이 100,000인 만큼 단순하게 배열을 이용해 최댓값, 최소값을 찾는 방식은 시간초과가 날 것 입니다. 따라서 우선순위 큐를 도입하여 풀이를 해야합니다.

 

최소 힙

import heapq, sys
input = sys.stdin.readline

heap = []
for _ in range(int(input())):
    x = int(input())
    if x == 0:
        if heap:
            print(heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, x)

최대 힙 

파이썬의 경우 heapq가 최소 힙을 만들어주기 때문에 최대 힙을 구현하려면 아래의 코드 14번 라인과 같이 음수로 값을 heap에 집어넣어준 뒤 값을 뽑을 때 다시 양수로 고쳐주는 방식을 사용합니다.

import heapq, sys
input = sys.stdin.readline

heap = []
for _ in range(int(input())):
    x = int(input())
    if x == 0:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(0)
    else:
        # 원소를 음수로 넣어주면 최소힙을 최대힙처럼 구현가능
        heapq.heappush(heap, -x)

 

---

Python heapq에 대한 포스팅

[Python] heapq 모듈