[#15903] 카드 합체 놀이

RookieAND·2022년 7월 2일

백준 우선순위큐 코테 힙

BaekJoon

목록 보기

23/42

❓ Question

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

📖 Before Start

우선 순위 큐를 사용하여 가장 작은 수를 추출해야 하는 문제.

이번 문제는 우선순위 큐와 힙 자료구조을 사용하여 풀어야 하는 문제였다.
처음으로 학습하는 알고리즘인 만큼, 더 다양한 문제를 풀기 위해 도전했다.

✒️ Design Algorithm

두 카드를 꺼내 값을 합하고, 이를 도로 카드 더미에 넣어야 한다.

순차적으로 카드의 값을 입력 받아 List 에 저장하되, 두 카드를 뽑는 과정을 유의하였다.
뽑힌 두 카드의 숫자를 합한 후, 이를 다시 List 에 넣어주는 것을 M 번 반복한다고 한다.

이러한 과정을 거친 후, 카드 더미의 값을 모두 합산한 값이 최소가 되도록 해야 한다.
그러면, 카드 더미 중에서 가장 작은 값이 담긴 카드 두 장을 뽑아야만 된다는 소리다.

N 개의 자연수가 담긴 우선순위 큐에서, 가장 값이 작은 두 장을 뽑는다.
이후 두 값을 합산하여 나온 결과값을 다시 우선순위 큐에 두 차례 넣는다.
이를 M 회 반복한 후, 우선순위 큐 내의 값을 모두 합산한 결과를 출력시킨다.

Python에서 지원하는 heapq 라이브러리는 이진 트리 기반의 최소 힙 자료 구조를 지원한다.

heappush(heap, elm) : 힙 자료구조에 새로운 원소를 추가하는 함수다.
heappop(heap) : 힙 자료구조에서 가장 값이 작은 원소를 삭제시킨다.

추가적으로, heapq 라이브러리를 최대 힙처럼 쓰고 싶다면 다음과 같이 코드를 작성해야 한다.

import sys
import heapq

read = sys.stdin.readline
N = int(read())

heap = []
for _ in range(N):
    x = int(read())
    if x != 0:
        if not heap:
            print(0)
        else:
            _, num = heapq.heappop(heap)
            print(num)
        continue
    heapq.heappush(heap, (-x, x))

이렇게 tuple (우선 순위 기준, 값) 형태의 원소를 집어넣어서 우선순위 큐를 구현하면 된다.
이럴 경우 heapq 라이브러리는 튜플 원소의 0 번째 인덱스를 우선순위 기준으로 판단한다.

해당 코드는 앞에 - 를 붙여, 절댓값이 클수록 우선 순위로 쓰이는 값을 더 작게 설정하였다.
따라서 heappop() 사용 시 가장 작은 값이 담긴 튜플이 나오고, 실질적인 값인 1 번째 인덱스를 사용하였다.

해당 문제는 백준 11279번 문제인 최대 힙 문제의 정답 코드이다. 겸사겸사 여기다가도 넣는다.

💻 Making Own Code

✅ Correct Code

import sys
import heapq

read = sys.stdin.readline
N, M = map(int, read().split())
# 먼저, 우선순위 큐를 위해 heap에 값을 추가.
heap = []
for cd in list(map(int, read().split())):
    heapq.heappush(heap, cd)

for _ in range(M):
    # 우선순위 큐에서 가장 작은 수 2개를 추출
    f_card = heapq.heappop(heap)
    s_card = heapq.heappop(heap)
    # 두 수의 합을 우선순위 큐에 두 차례 추가함.
    max_card = f_card + s_card
    heapq.heappush(heap, max_card)
    heapq.heappush(heap, max_card)

print(sum(heap))

나는 처음 우선순위 큐로 사용할 List 를 먼저 비운 후 순차적으로 값을 추가해야 했는데,
heapq 라이브러리의 heapify() 함수를 사용하면 기존의 List 를 Heap 으로 바꿔주더라.

다음부터는 꼭 저 함수를 써먹고야 말겠다. 왜 이런 꿀같은 기능을 이제야 알았을까?

# 기존의 코드, 빈 List를 생성하고 heappush로 값을 대입한 모습이다.
heap = []
for cd in list(map(int, read().split())):
    heapq.heappush(heap, cd)
    
# 새로운 코드, 훨씬 더 심플하고 간결해지고... 하여튼 사기 함수다.
heap = heapq.heapify(list(map(int, read().split())))