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

1. 문제정보

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

1715번: 카드 정렬하기

 

 

2. 해결전략

처음 생각했던 전략은 리스트를 오름차순으로 정렬하고 합계를 더해가는 방식으로 구현했습니다. 입력 횟수가 최대 10만번 이기 때문에 입력 시간을 줄이기 위해 readline을 사용했지만 리스트를 이용한 방법은 연산 횟수가 최대 10만x10만으로 시간 초과를 받았습니다. 결국 우선순위큐에 대한 힌트를 확인한 후 우선순위큐로 구현하였습니다. 

 

 

3. 코드

import sys
from queue import PriorityQueue

input = sys.stdin.readline
n = int(input())
q = PriorityQueue()

for _ in range(n):
    card = int(input())
    q.put(card)


result = 0
if q.qsize() == 1:
    print(0)
else:
    while q.qsize() >= 2:
        n1 = q.get()
        n2 = q.get()
        result += (n1+n2)
        q.put(n1+n2)
    print(result)