(Python)[백준][우선순위 큐] 카드 정렬하기

1715번: 카드 정렬하기

정답 비율: 33.966%

문제 풀이

---

처음에는 작은 값부터 더해주면서 리스트로 문제를 풀고자 했다. 근데 시간초과도 아니고 틀린 답안이라고 한다.

나중에 알아보니 정렬을 계속 해줘야 하는데 그게 이루어지지 않아서 안되는 것이었다. 왜냐하면 묶여서 새로운 값이 생길 때마다 그 값과 나머지 값들을 포함해서 제일 작은 값들끼리 묶어야 하므로 계속 정렬을 해줘야 한다.

이전 풀이

import sys
from tempfile import tempdir

input = sys.stdin.readline
# 숫자 카드 묶음 개수 N 입력받기
n = int(input())
# 카드 묶음의 크기 입력받기
cards = []
for _ in range(n):
    cards.append(int(input()))

# 작은 값부터 더해주기 위해 오름차순 정렬
cards.sort()

if len(cards)==1:
    print(0)
else:
    answer = cards[0] + cards[1]
    sum_counts = answer
    for i in range(2, n):
        sum_counts += cards[i]
        answer += sum_counts

    print(answer)

우선순위 큐(heapq)를 이용하여 풀어본다. heapq를 사용하면 push가 될 때 자동으로 정렬이 되므로 계속 정렬을 해줄 필요가 없다.

소스 코드

import heapq 

n = int(input())
cardList = []
for i in range(n):
    card = int(input())
    heapq.heappush(cardList, card)

answer=0
while len(cardList) != 1:
    num1 = heapq.heappop(cardList)
    num2 = heapq.heappop(cardList)
    sum_value = num1 + num2
    answer += sum_value
    heapq.heappush(cardList, sum_value)

print(answer)