백준 카드 정렬하기 코드 및 해설 (파이썬)

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

1715번: 카드 정렬하기

 

cards라는 heap에 각 카드 묶음의 카드 수를 저장합니다. cards의 길이가 1이 될 때까지 다음을 반복합니다.
최솟값 2개를 뽑아(pop) 둘의 합을 result라는 리스트에 추가하고, 둘의 합을 cards 힙에도 다시 추가합니다. 이후 다시 최솟값 2개를 뽑아 이를 반복합니다.
마지막엔 result 리스트의 모든 원소의 합을 반환합니다.

• sort 함수를 이용하면 시간초과가 되고, heap을 이용하면 통과가 되었습니다!

 

import sys
import heapq

# 카드 묶음의 개수
N = int(sys.stdin.readline())
# 각 카드 묶음의 크기
cards = []
for i in range(N):
    cards.append(int(sys.stdin.readline()))
heapq.heapify(cards)

result = []
while len(cards) > 1:
    # 최솟값 2개 뽑아 섞기
    mix = heapq.heappop(cards) + heapq.heappop(cards)
    result.append(mix)
    # 섞은 뭉텅이를 다시 cards에 넣기
    heapq.heappush(cards, mix)

print(sum(result))