[이것이 코딩테스트다] 15일차 - 우선순위 큐 | 백준 카드정렬하기

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 6 정렬

오늘 풀이한 문제

[백준 1715] 카드 정렬하기

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

 

접근 방법

- 처음에는 문제 접근을 잘못해서 정렬 후 무작정 더할뻔했다

- 반복문을 이용하여 [ 맨 앞 두 요소를 빼고 이를 더한값을 맨 앞에 넣고 ]를 반복하면 되겠다는 생각을 했는데 insert()와 pop()로 어떻게 해야할지 막막했다,, 검색해보니 파이썬에는 heapq라는 라이브러리가 있었다!

- 다른분들의 풀이를 참고하여 코드를 짜고 (핵심 흐름은 같았기에 금방 짤수있었다) 우선순위 큐에 대해 공부하였다 

 

소스 코드

N = int(input())
card = [int(input()) for _ in range(N)]

import heapq 
heapq.heapify(card)
result = 0

while len(card) != 1:
    n1 = heapq.heappop(card)
    n2 = heapq.heappop(card)
    sum_n = n1+n2
    result += sum_n 
    heapq.heappush (card, sum_n)

print (result)

 

우선순위 큐 (Priority Queue)

우선순위를 가지는 데이터를 먼저 추출하는 구조를 가진 자료구조이다

자료구조	추출되는 데이터
스택	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은 데이터

우선순위 큐는 일반적으로 힙(heap)을 이용하여 구현한다 

힙 (Heap)

- 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다

포화이진트리	모든 잎의 레벨이 동등한 이진트리, 잎이 아닌 내부 노드들은 모두 2개의 자식을 가지는 트리
완전이진트리	포화이진트리의 leaf들을 오른쪽에서부터 제거하여 얻어진 트리

 

- 부모 노드와 서브트리간의 대소관계가 성립된다 (반정렬 상태)

 

힙의 종류

- 최대 힙 (Max Heap) : 부모노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리 -> 가장 큰 값이 가장 먼저 삭제

- 최소 힙 (Min Heap) : 부모노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리 -> 가장 작은값이 가장 먼저 삭제

 

힙의 삽입

(최소힙 기준) 힙을 삽입할때 부모노드보다 삽입된 힙이 작은값을 가지는 경우 최소힙의 조건을 만족하기 위해 부모노드와 노드를 교체한다 

 

힙의 삭제

루트 노드자리에 가장 마지막 노드를 넣고, 힙의 성질을 유지하기 위한 연산을 수행한다

 

루트 노드자리에 가장 마지막 노드를 넣음

힙의 성질을 유지

힙의 삭제와 삽입은 시간복잡도 O(logN)을 가진다

 

파이썬 힙 라이브러리 (heapq) - defulte 최소힙

heapq — 힙 큐 알고리즘 — Python 3.9.9 문서

- 기존 리스트를 힙으로 변환 

     heapq.heapify(list)

- 힙 원소 삽입

     heapq.heappush(heap, item)

- 힙 원소 삭제 (가장 작은항목 반환)

     heapq.heappop(heap)

     가장 작은 값을 반환하지 않고 접근만 하기위해서는 heap[0] 하면 됨

- 힙 원소 삽입 + 삭제 -> 힙에 item을 삽입하고 가장 작은 항목을 반환

     heap.heappushpop(heap, item)

 

최대힙 구현

힙에 원소를 튜플로 제공하면 튜플의 맨 앞의 값을 기준으로 최소힙이 구성됨

-> 튜플을 (-num, num)으로 구성하고 원소로 추가 

-> pop 후 튜플의 index 1값을 읽어오면 됨

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1

참고 사이트 

[파이썬] heapq 모듈 사용법