[백준 - Python] 1715. 카드 정렬하기 (그리디)

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

1715번: 카드 정렬하기

 

코드

from heapq import heappush, heappop
import sys

card = []

n = int(input())
for _ in range(n):
    heappush(card, int(sys.stdin.readline()))

total = 0
while len(card)>1:
    first = heappop(card)
    second = heappop(card)
    sum = first + second
    heappush(card, sum)
    total += sum
print(total)

 

문제를 보고 아이디어도 떠올리고 구현도 해서 문제 예시도 다 돌아갔는데 계속 출력 초과가 났다.

답답함에 다른 분들 풀이를 참고했는데,

heapq를 활용해야 했었다.

 

출력 초과는 출력 되어야 할 출력값 이상으로 추가적인 출력이 나온다는 것이라는데,

왜 같은 논리를 heapq를 활용하면 통과되고 heapq를 활용하지 않으면 통과가 안되는 건지 모르겠다.

heapq를 사용하지 않은 것이 느려서 통과가 안되는 거라면,

시간 초과가 떠야하는 거 아닌가?

 

heapq를 활용해서 직관적으로 풀면 수월하게 풀리는 문제였다.

heappush를 해줄 때 total이 아니라 sum을 넣어줘야 하는 부분만 유의해서 보자.

 

heapq 자료구조를 활용해 풀 수 있고

그렇게 풀면 시간 단축이 가능하겠다는 생각을

처음부터 떠올렸으면 좋았겠다!