크래프톤정글 2주차; 파이썬 최소 힙, 최대 힙, 우선순위 큐 모듈 및 관련 문제

파이썬에서 heapq 모듈로 최소 힙, 최대 힙 구현하기

출처:https://velog.io/@yyj8771/Python-heapq를-이용한-최소-힙-최대-힙

무엇?

1. heapq
   1. 최소 힙, 최대 힙을 만들 때
   2. 주의할 점은 디폴트에 최소 힙 구현에 맞춰져 있어서, 최대 힙을 만드려면 push할 때 -1을 곱한 값으로 넣어주고, pop할 때도 -1을 곱한 채로 빼야 정상 작동함!
   3. pop할 때 배열이 비어있으면 인덱스 에러 뜸
   4. heap = [] 힙으로 사용할 배열 선언
   5. 메소드
      • heapq.heappush(배열, 값) : 최소 힙에 push
      • heapq.heappop(배열) : 최소 힙에서 가장 최솟값 pop
      • heapq.heappush(배열, -값) : 최대 힙에 값 push
      • -heapq.heappop(배열) : 최대 힙에서 가장 최댓값 pop (앞에 마이너스 부호 붙은 거 주의!)

왜?

백준 최대 힙 문제 풀다가, 한땀 한땀 책에 나온 슈도 코드를 보면서 최대 힙 만드는 함수를 구현했는데,
시간 초과로 실패함.
룸메이트님이 보시고 그거 모듈 쓰면 쉽다고 했다. ㅎㅎ
허탈했다. 하지만 그렇게 붙잡고 있던 덕분에 그나마 힙 구조와 친해진 듯.

어떻게?

0을 입력하면 pop하고 정수를 입력하면 push하며 최대 힙 구조를 유지하는 프로그램

import sys
import heapq

N = int(sys.stdin.readline())
heap = []

for _ in range(N):
    input = int(sys.stdin.readline())
    heap_size = len(heap)
    if input == 0:
        if heap_size == 0:
            print(0)
        else:
            print(-heapq.heappop(heap))
    else:   # 정수를 삽입할 때
        heapq.heappush(heap, -input)

파이썬에서 PriorityQueue 모듈로 우선순위 큐 구현하기

출처: https://www.daleseo.com/python-priority-queue/
https://johnyejin.tistory.com/72

무엇?

1. PriorityQueue
   1. from queue import PriorityQueue
   2. 가장 작은 숫자의 우선순위를 가진 원소가 나가게 됨(최소 힙 형태)
   3. 우선순위 큐는 인덱스로 접근 불가능(ex: que[0] 같은 것 안됨!)
   4. iterable하지 않음. get으로 제일 작은 거부터 빼는 것만 가능하다고 함
   5. 메소드
      1. que = PriorityQueue(maxsize = 8) : 최대 크기 설정하고 싶으면 지정
      2. que.put((2, "apple")) : (우선순위, 값) 형태로 튜플로 우선순위와 값을 지정해 넣을 수 있음
      3. que.get() : 가장 작은 숫자를 가진 원소 출력
      4. que.qsize()
      5. que.empty()
      6. que.full()

왜?

백준 우선순위 큐 문제에서 사용해보려고 찾음.
그런데 백준에서 해당 모듈 지원 안 한다. ㅠㅠ
하지만 최소 힙 형태이므로 heapq 모듈을 사용하면 된다.

어떻게?

백준 1715번 카드 정렬하기 파이썬 풀이 참고

출처: https://velog.io/@yeseolee/python-자료구조-우선순위-큐Priority-Queue

무엇?

백준 1715번 최소 힙 이용하기

왜?

정답 코드를 보면 하나의 최소 힙만 사용했고,
더한 값을 다시 그 최소 힙에 넣어서 쉽게 계속 최소 값끼리 더할 수 있게 만들었음.
나는 오로지 입력된 카드 더미의 수를 담는데만 최소 힙을 쓰고,
그 외의 횟수 연산을 위해 일반 리스트를 두개나 사용했다.
따라서 별로 효율적이지 못했음. (코드 짜면서도 시간 초과 뜰 거 같았는데 역시 뜸)
또 더한 값도 최소 힙을 이용해야 계속 최소값끼리 더할 수 있게끔 보장되는데,
나는 그렇게 안 했기 때문에 시간 초과 문제를 떠나 예제는 맞아도 정확하지 않음.

어떻게?

▽ 내 코드 중 문제의 부분.
다시 보니 temp, count를 그냥 하나의 int 값을 담는 count 변수만 사용해도 됐겠다.

minheap = []
temp = []
for i in range(2):
    pop_out = heapq.heappop(minheap)
    temp.append(pop_out)
count = []
count.append(sum(temp))

while len(minheap) != 0:
    pop_out = heapq.heappop(minheap) 
    count.append(sum(count)+pop_out)

print(sum(count))

▽ 수정 후

count = 0
while len(minheap) != 1:  
    pop_out1 = heapq.heappop(minheap)  #최소 값 두 개씩 빼서 더함
    pop_out2 = heapq.heappop(minheap)
    count += (pop_out1 + pop_out2)
    heapq.heappush(minheap, pop_out1 + pop_out2)
print(count)