[Python] 1715번 : 카드 정렬하기

 

문제 3줄 요약

1. 두 묶음(A,B)의 숫자 카드를 합치려면, A+B 만큼의 비교가 필요하다.

2. A(10), B(20), C(40) 세 묶음을 비교하는 최소는(A(10)+B(20)) + (A+B(30)+C(40)) = 100이다.

3. N개의 숫자 카드 묶음의 최소 비교 수는 몇 일까?

 

 

 

 

비교 횟수가 최소가 되는 경우는

묶음의 수가 작은 묶음끼리 비교하는 것이다.

 

왜냐하면!

더해진 묶음을 결국 다른 묶음과 비교를 해야하는데,

숫자가 많은 카드 묶음은 가장 나중에 비교를 하는만큼 그 숫자만큼 덜 더한다.

 

그렇다면, 카드 묶음을 오름차순으로 정렬하고

더해주는 것을 반복해주면 되지 않나?

 

매번 비교를 해준 결과를 반복문을 통해 자리를 찾아주거나,

리스트의 첫 번째 원소를 가져오는 pop(0)을 연산을 할 경우

N의 수가 최대 10만 이기 때문에,

시간 초과가 생긴다.

 

이런 경우에 사용하기 적합한

이진 트리로 값을 정렬 해주는 자료구조인 headq, 우선순위 큐를 사용하자!

 

https://velog.io/@mein-figur/Python%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-heapq

[Python]우선순위 큐, heapq

 

사용법은 위를 참고하면 될 것!

 

처음엔 deque를 사용하여 popleft만 해결하였더니,,

값을 정렬하는 과정에서 

 

 

시간 초과 ㅎ..

 

바로 우선순위 큐를 사용해주니

통과하였다!

 

 

from sys import stdin
from queue import PriorityQueue

if __name__ == "__main__":
    N = int(stdin.readline())

	# 카드 묶음을 담을 우선순위 큐
    card_q = PriorityQueue()
    for _ in range(N):
        card_q.put(int(stdin.readline()))

    result_list = []
    while(True):
        if card_q.empty():
            break
        
        # 비교할 첫 번째 묶음
        A = card_q.get()

        if card_q.empty():
            break
		# 비교할 두 번째 묶음
        B = card_q.get()

        result_list.append(A+B)
        # 묶어진 카드 묶음 다시 넣기
        card_q.put(A+B)
    
    print(sum(result_list))

 

끝!