★PQ 중상급 - 6문제()★

🧠 priority queue를 구현하기 위한 heap 관련 여러 문제는 기존 자료구조(stack, queue, deck)보다 더 복잡한 tree구조로, 중급 이하의 문제는 없다. 중상급 이상부터 여러 문제를 풀며 적응해보자

 

🧠 priority queue 관련 개념 포스팅 참고

priority queue - (binary) heap tree

---

★ 1927 최소 힙 ★

 

import sys
import heapq
input=sys.stdin.readline

N=int(input())
arr=[]
heap=[]

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

 

 

🧠 heapq library를 구현하고, 크게 두 가지 경우에 따라 heap 관련 함수를 쓰면 됨

 

① x가 자연수라면(x>0) heappush()를 사용해 list로 구현한 heap에 x를 집어넣는다

② x가 0이라면, heap에 element가 있을 경우 heappop()으로 뽑은 뒤, 해당 결과를 바로 출력! 아니면 0을 출력

 

🧠 python의 heapq는 min-heap에 맞추어져 있다.

 

---

★ 11279 최대 힙 ★

 

import sys
import heapq
input=sys.stdin.readline

N=int(input())
arr=[]
heap=[]

for _ in range(N):
    x=int(input())
    if x>0:
        heapq.heappush(heap,-x)
    else:
        if len(heap)>0:print(-heapq.heappop(heap))
        else:print(0)

 

 

🧠 위 1927 최소 힙 코드에서 heappush에 들어가는 value에 -를 붙이고, heappop으로 나오는 value에 -를 붙이면 끝!

---

★ 14235 크리스마스 선물 ★

 

import sys
import heapq
input=sys.stdin.readline

n=int(input())
heap=[]

for _ in range(n):
    a=list(map(int,input().split()))
    l=len(a)
    if l>1:
        for i in range(1,l):
            heapq.heappush(heap,-a[i])
    else:
        if len(heap)>0:print(-heapq.heappop(heap))
        else:print(-1)

 

🧠 선물을 주되, 가장 가치가 큰 선물 먼저 줘야 하므로, 단순한 자료구조가 아닌, 우선순위 가 있는 우선순위 queue heap 구조 사용!

---

★ 23757 아이들과 선물 상자 ★

 

import sys
import heapq
input=sys.stdin.readline

N,M=map(int,input().split())
c=list(map(lambda a: -int(a),input().split()))
w=list(map(int,input().split()))
y=0

heapq.heapify(c)

for i in range(M):
    popped = heapq.heappop(c)
    if -w[i] < popped:
        print(0)
        y+=1
        break
    heapq.heappush(c,popped+w[i])

if y==0:print(1)

 

🧠 차례대로가 아니라, 선물이 가장 많이 담겨 있는 상자를 매번 선택해야 하므로 우선순위 큐 구현 idea

 

🧠 삽입과 삭제 연산 heappop & heappush는 모두 O(logN) 시간 복잡도를 보이므로(heap binary tree 구조 장점), 이 두 연산을 최대한 활용해서 code 시간 단축

 

🧠 여기서 max-heap을 구현해야 하므로, 처음에 lambda 식으로 음수만 입력받음. 이어서 부등호 대소 비교와 w에 음수 붙이는 거 적절히 고려! (python의 heapq는 min-heap이므로 잘 변형해줘야 함)

 

import sys
import heapq
input=sys.stdin.readline

N,M=map(int,input().split())
c=list(map(lambda a: -int(a),input().split()))
w=list(map(int,input().split()))
y=0

heapq.heapify(c)

for i in range(M):
    if -w[i] < c[0]:
        print(0)
        y+=1
        break
    c[0]+=(w[i])
    heapq.heapify(c)

if y==0:print(1)

 

🧠 위 code는 시간 초과가 나온 code로, heapify() 함수를 사용. heapify()의 time complexity는 O(N)으로, 이 는 sorting에서 heap을 사용한 의미가 아예 없기 때문에 (그냥 정렬 sorting 시간 복잡도는 O(N)이다. 추후 정렬 정리 포스팅 참조) 당연히 시간 초과. 주의하자!

---

★ 11286  절댓값 힙 ★

 

import sys
import heapq
input=sys.stdin.readline

N=int(input())
heap=[]

for _ in range(N):
    x=int(input())
    if x!=0:
        heapq.heappush(heap,[abs(x),x])
    else:
        if len(heap)>0:print(heapq.heappop(heap)[1])
        else:print(0)

 

🧠 max-heap, min-heap이 아닌 절댓값 heap을 구성할 수 있다.

 

🧠 heappush의 두번째 인자를 tuple의 형태로 넣어, tuple의 첫번째 인자에 의해 heap이 완성되고, 첫번째 인자가 같을 경우, tuple의 두번째 인자를 기준으로 heap이 구성된다.

 

🧠 아래 docu 내용 참조

 

- 출처) https://docs.python.org/2/library/heapq.html#basic-examples

 

🧠 따라서, heappush() 사용 시 tuple을 사용해 heap을 구성할 수 있다는 점. 기억하자! 위 문제는 먼저 절댓값으로 heap을 구성하고, 만약 같을 경우 두 번째 인자인 x, 즉 x가 작은 경우 먼저 heappop() 될 수 있도록 구성했다.

---

★ 15903 카드 합체 놀이 ★

 

import sys
import heapq
input=sys.stdin.readline

n,m=map(int,input().split())
l=list(map(int,input().split()))
heapq.heapify(l)

for _ in range(m):
    a = heapq.heappop(l)
    b = heapq.heappop(l)
    heapq.heappush(l,a+b)
    heapq.heappush(l,a+b)
print(sum(l))

 

🧠 greedy 유형과 합친 문제로, 작은 점수가 나올려면, 매번 카드를 뒤집을 때마다 제일 크기가 작은 두 수를 선택해 서로 합한게, 당연히 전체 합의 최소가 된다.

 

🧠 sort()보다 heappop & heappush 자료구조 heap을 사용해 시간을 단축하였고, 매번 heappop(), heappush()를 할 때마다 complete-binary tree 형태의 heap을 완성하므로, 매 케이스마다 최솟값을 가져오는데 시간 효율적인(O(logN)) 자료구조이다.

 

---