Q26. [백준]카드 정렬하기

정렬하기 문제를 풀러가기 전에, 힙에 대해 정리해보도록 하겠다. 정렬하기 문제에서 무조건 sorted함수나 deque만 사용할 수 있다고 생각하면 간단하게 못 푼다ㅠㅠ

heapq 자료구조?

heapq은 이진트리 기반의 자료구조이다. 구현하고자하는 heapq이 최소 힙이냐, 최대 힙이냐에 따라 루트노드가 달라진다.
1. min heap : 가장 작은 원소가 루트노드에 위치하게 됨
2. max heap : 가장 큰 원소가 루트노드에 위치하게 됨

원소 추가, 삭제

heapq의 원소 추가, 삭제는 덱 자료구조와 비슷하다. push와 pop을 이용하면 된다. 이 아이도 덱과 마찬가지로 리스트를 한번에 넣는 것도 가능하다.

import heapq

heapq.heappush(heap,5)
heapq.heappush(heap,7)
heapq.heappush(heap,9)
heapq.heappush(heap,1)
print(heap)

결과값은 [ 1, 5, 9, 7 ]이 된다. 가장 작은 원소가 인덱스 0에 위치하게 되며, 인덱스 1에 있는 5가 인덱스 3에 있는 7보다 작기 때문에 이는 힙 자료구조를 만족한다.

print(heapq.heappop(heap))
# 1

힙에서 제거 함수를 사용하면 가장 작은 루트 노드가 출력된다.

카드 정렬하기

문제를 본격적으로 풀어보면, 가장 작은 크기의 두 카드 묶음을 먼저 묶었을 경우 최적의 해를 보장한다는 것이다. 나 같은 경우 처음 문제를 풀 때 '그냥 모든 경우의 수를 계산해보자' 라는 1차원적인 생각을 하고 순열 라이브러리를 사용해서 풀었지만 다시 한번 생각해보면 정말,,, 정렬하기 문젠데 그럴 리가 없다. 그리고 2묶음씩 묶는 것이 이 문제의 키 포인트이므로 이진트리 자료구조인 heapq을 사용하는 것이 가장 좋다는 결론에 도달하게 된다.

테스트 케이스 예시를 힙 자료구조로 나타낸 것이다.

카드 묶음을 heapq을 사용해서 넣는 코드는 다음과 같다.

import heapq

n = int(input())

# 힙(Heap)에 초기 카드 묶음을 모두 삽입한다.
heap = []
for i in range(n):
  data = int(input())
  heapq.heappush(heap, data)

input값으로 받은 카드를 힙에 하나씩 삽입한다.

그리고 힙의 길이가 1이 될 때까지 힙에서 가장 작은 값 두개를 꺼내서 합치고, 힙에 넣는 과정을 반복해주면 된다. 이 과정에서 변수를 구분 잘 해야한다..

result = 0
while len(heap) != 1:
  # 가장 작은 2개의 카드 묶음을 꺼내기
  one = heapq.heappop(heap)
  two = heapq.heappop(heap)
  # 카드 묶음을 합쳐서 다시 삽입
  sum_value = one + two
  # 합친 카드를 result에 더함
  result += sum_value
  heapq.heappush(heap, sum_value)

print(result)