1715번 카드 정렬하기

문제 출처 : https://www.acmicpc.net/problem/1715

사고과정

처음에는 별생각없이 sort해서 앞에서부터 차례대로 더해나가면 되는거 아닌가 싶어서 짰지만 바로 '틀렸습니다' sort한다고 해도 묶음을 앞에서만 더했을 때 최솟값이 발생하는 게 아니란 걸 깨달았다. A,B,C,D,E...가 있다 치면 (A+B),(C+D),E... 이런 식으로 묶음을 비교할 수 있다. 일반화하여 생각해보면 결국 우리는 '최소한의 비교'를 해야하기 때문에 그때그때 묶음의 비교횟수가 가장 작아야 한다. 즉 모든 묶음 중 가장 작은 두개를 택해 비교한 횟수를 만든다!

어떻게 코드를 짜야할까 여러 방면으로 고민하던 차(시행착오가 김, deque쓸라고 하고 케이스 나눠서 어떻게 하면 시간복잡도를 줄일지.. )에 최솟값을 효율적으로 계산하는 우선순위 큐를 이용하면 쉽게 작성할 수 있겠구나! 싶어서 작성하였지만 역시나 동일하게 8%에서 틀렸다. 어떤 값에서 틀리는걸까?

문제를 잘못 풀었다. 수정!했는데 100퍼에서 틀림...??

아... 예외처리를 제대로 못했다...!!! 집중력이 흐트러져서 놓쳤다. 카드 묶음이 하나라면 비교를 하지 않으므로 0이 출력돼야한다.

import heapq
import sys

N = int(sys.stdin.readline().rstrip("\n"))

card = [int(sys.stdin.readline().rstrip("\n")) for _ in range(N)]
heapq.heapify(card)
result=0

if len(card)==1 :
    card=[0]
while len(card)>2 :
    c=heapq.heappop(card)+heapq.heappop(card)
    result+=c
    heapq.heappush(card,c)
for i in range(len(card)) :
    result+=card[i]
print(result)

동일한 logic인데 왜 rlatpgus4564님은 시간이 4128ms일까?
-> input()이 sys.stdin.readline().rstrip("\n")보다 무겁게 돌아간다.