[Python] 백준 1715번 : 카드 정렬하기

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

1715번: 카드 정렬하기

---

 문제 풀이

그리디 알고리즘 문제이다.

 

비교 횟수가 가장 작으려면 가장 작은 값들부터 먼저 계산해야 한다.

단 하나의 값이 남을 때까지 가장 작은 값 2개를 계산, 추가 그리고 저장을 반복한다.

일반적인 배열로 처리할 경우 시간 초과가 발생한다.

정렬하는 과정을 우선순위 큐에 맡겨주면 시간 초과가 발생하지 않는다.

 느낀 점

우선순위 큐를 모듈로 사용해서 쉬운 거지 직접 구현하려면 어려웠을 것 같다.

이번 기회에 파이썬에서 사용하는 힙 큐에 대해서 공부할 수 있어서 좋았다.

 코드

import sys, heapq

N = int(sys.stdin.readline())
cards = [int(sys.stdin.readline()) for i in range(N)]
heapq.heapify(cards)
cnt = 0

while len(cards) > 1:
    tmp = heapq.heappop(cards) + heapq.heappop(cards)
    heapq.heappush(cards, tmp)
    cnt += tmp
    
print(cnt)