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

드디어 골드문제 도전!

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

1715번: 카드 정렬하기

풀이

from queue import PriorityQueue

n = int(input())

card = PriorityQueue()

lst = []

for _ in range(n):

    card.put(int(input()))

for i in range(n-1):

    temp = card.get(card)+card.get(card)

    card.put(temp)

    lst.append(temp)

print(sum(lst))

처음에는 이렇게 풀었다. 우선순위 큐로 풀었는데 시간이 너무 오래 걸려서 heapq로 재도전!

from heapq import *

n = int(input())

card = []

lst = []

for _ in range(n):

    heappush(card,int(input()))

for i in range(n-1):

    temp = heappop(card)+heappop(card)

    heappush(card,temp)

    lst.append(temp)

print(sum(lst))

리스트를 힙 형태로 만들지 않고 pop하려하면 제대로 pop이 이루어지지 않는다는 걸 이번에 배웠다...ㅠㅠ

만약 heappush(card, int(input()) 을 안쓰고

card.append(int(input())) 으로 데이터를 입력받으면

heapify() 를 써서 heap형태로 만들어서 정렬해줘야한다는 걸 알게 되는 문제였음.

 

하... 그런데 시간이 단축되지 않는다... 나중에 좀 더 연구해봐야할듯..ㅠㅜ