문제풀이) 백준 - 1715 / 카드 정렬하기

문제링크

문제 요약

1. 비교시 두 카드 뭉치의 합만큼 비교를 해야한다.
2. 주어진 카드 뭉치 모두를 비교 할 때 가장 최소한으로 비교한 값을 구하라.

어떻게 풀어야 할까?

먼저 합친 카드 뭉치가 적으면 적을수록 바교 횟수가 줄어듬으로 오름차순으로 정렬해서 풀어야 할 듯하다

코드

import heapq

n = int(input())
cards = [int(input()) for _ in range(n)]
heapq.heapify(cards)
sum = 0
result = 0

while len(cards) != 1:
  sum = heapq.heappop(cards) + heapq.heappop(cards)
  result += sum
  heapq.heappush(cards, sum)

print(result)

코드 풀이

heapq 모듈 사용
line 8. 더이상 합칠 카드가 없을 때까지 반복하는 반복문
line 9-11. heapq.heappop(list)가 반환하는 min값을 두 번 더한 (두 카드 뭉치를 더하는 문제임으로)
sum 변수를 결과값에 더해주고 cards heap에 넣어주는 식으로 풀이하였다. 

피드백

합친 카드 뭉치도 정렬해서 계산해야 한다는 부분을 놓쳐서 시간이 걸렸다.
-> 문제 이해력!!!
반복적으로 정렬을 해야하는 문제이기 때문에 heapq 모듈을 사용해서 풀었는데, 문제풀이에 자주 이용 할 수 있는 
모듈이라고 생각되었다.
-> heapq 사용법 익히기 ( 아래 사이트에 max heap, k번째 수, 힙정렬과 같은 내용이 있음! )

heapq 설명 및 활용