[백준 : 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)