[백준/Python] 카드 정렬하기

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

import heapq

# 입력받는 부분
n = int(input())
cards = []
for i in range(n):
  heapq.heappush(cards, int(input()))
answer = 0 # 최소 비교 횟수
  
 # 최소 비교 횟수 계산
while len(cards) != 1:
  first = heapq.heappop(cards)
  second = heapq.heappop(cards)

  result = first + second
  answer += result
  heapq.heappush(cards, result)

# 최소 비교 횟수 출력
print(answer)

 

어떻게 코드를 짜야할지 직관적으로 보이긴 하지만 제가 처음 생각한 방법은 약간 노가다같은 느낌이 들었습니다. 그래서 다른 사람들의 풀이를 보니까 힙을 사용해야하는 것을 알았습니다. 힙을 코드로 사용해본 적이 없었어서 힙을 공부한 후 코드를 짰습니다.

 

이 문제는 힙을 사용하면 로직이 그렇게 어려운 문제는 아니었습니다. 이 문제에서는 최소 힙을 사용합니다. 먼저 카드 묶음 수와 각 카드 묶음의 수를 입력받아 힙에 저장합니다. 힙의 길이가 1이면 더 이상 계산할 값이 없고 저장되어 있는 1개의 값이 최소 비교 횟수입니다. 따라서 while문을 통해 힙의 길이가 1이 될 때까지 힙에서 두 개의 값을 뽑아 더한 값을 구하고 그 더한 값을 다시 힙에 저장하는 것을 반복합니다.  힙의 길이가 1이 되면 while문을 빠져 나오고 최소 비교 횟수를 출력합니다.

 

- 배운 점 -

Heap (힙)

우선순위 큐 방식 중 하나가 힙입니다. 우선순위 큐는 데이터가 들어간 순서에 상관없이 우선순위가 높은 순서대로 정렬되는 자료구조입니다. 데이터를 삭제할 때는 우선순위가 가장 높은 데이터부터 삭제됩니다. 힙은 최소 힙과 최대 힙으로 나눌 수 있는데, 최소 힙은 루트 노트가 가장 작은 값은 가지는 구조이고 값이 작을 수록 우선순위가 높아집니다.  반대로 최대 힙은 루트 노드가 가장 큰 값을 가지는 구조이고 값이 클수록 우선순위가 높아집니다. 힙에서 삭제를 할 때 우선순위가 높은 것부터 삭제되므로 항상 루트 노드부터 삭제됩니다.

 

import heapq

heap = [] # 힙 리스트 생성

# 힙에 값 저장
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heapq.heappush(heap, 4)
heapq.heappush(heap, 2)

print(heap) # [1, 2, 3, 4]

# 힙에서 값 빼기
first = heapq.heappop(heap)
second = heap.heappop(heap)

print(first) # 1
print(second) # 2

힙을 사용하기 위해서는 꼭! import 해줘야 합니다. 힙에 값을 넣을 때는 heapq.heappush(리스트명, 값) 를 사용하고, 힙에서 값을 빼고 싶을 때는 heapq.heappop() 을 사용하면 됩니다.