[백준 : PYTHON] 1715_카드정렬하기

문제링크 :

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

1715번: 카드 정렬하기

문제 :

풀이과정

문제풀이 로직

결과적으로 작은 값부터 더해야 최소 값을 만들 수 있으므로, 우선순위 큐를 활용.

최소 값 2개를 꺼낸 뒤, 이들을 더한 값을 다시 리스트에 추가 & 값 누적 하면 된다.

최소 값 두 개를 더한 값을 리스트에 다시 추가했기 때문에, queue의 길이가 1일 때까지 누적 값을 구한다. (누적 값에는 선 반영이 되어있기 때문)

 

내 풀이

import sys
from queue import PriorityQueue
def solution():
    input = sys.stdin.readline
    num = int(input())
    p_queue = PriorityQueue()
    answer = 0
    for i in range(num):
        p_queue.put(int(input()))
    
    while(p_queue.qsize() > 1):
        sum_val = p_queue.get() + p_queue.get()
        answer += sum_val
        p_queue.put(sum_val)
    return answer
    
print(solution())

 

다른 사람 풀이

다른 사람들은 PriorityQueue보다는 heapq를 활용해서 풀었다.

추가적으로 알아보니 파이썬은 heapq의 실행 속도가 더 빠르기 때문에 이를 더 많이 사용하는 듯 했다. ( JAVA- PriorityQueue 사용 )

import sys, heapq as hq

input = sys.stdin.readline
n = int(input())
cost = 0

cards = [int(input()) for _ in range(n)]
hq.heapify(cards)

while len(cards) > 1:
    tmp = hq.heappop(cards) + hq.heappop(cards)
    hq.heappush(cards, tmp)
    cost += tmp

print(cost)