백준 1715 - 카드 정렬하기

문제

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

풀이

문제이해

• 그리디 방법을 이용하여 문제에 접근
• 문제를 보면 각 묶음의 카드 수를 합치기 위해서는 각 카드 장 수를 합친 횟수만큼 비교를 실시해야한다.
• 그리고 각 카드 묶음에 대해 최소한 비교횟수를 요구한다.

문제접근

예제를 이용하여 문제에 접근하면 10,20,40장의 카드 장수를 가진 세 개의 카드 묶음이 있다.
문제에 대한 최적해는 우선 10+20으로 30번 비교하여 30장의 카드묶음으로 먼저 합친다. 그리고 30+40으로 70번 비교하여 총 100회 비교를 실시하여 카드묶음을 하나로 합칠 수 있다.

또한 문제에서는 잘못된 접근 방법에 대해 예시를 보여주고 있는데 (10 + 40) => (50 + 20)으로 총 120회 비교하여 최소한의 비교조건을 채우지 못하고 있다.

문제의 예시를 통해 우리는 카드 장수를 가장 적은 장수를 가진 카드 묶음끼리 합쳐야 최소한의 비교횟수를 가질 수 있다는 것을 확인할 수 있다.

구현 접근

위의 문제 접근을 통해 우리는 항상 어떠한 상황에서도 카드 장수가 적은 카드 묶음들만을 선택해야한다는 것을 알게 되었다. 그렇다면 어떻게 구현 할 것인가?

잘못된 접근

카드 묶음을 리스트로 받고, 리스트에 변화가 있을 때 마다 오름차순으로 정렬을 실시한다.

해당 방법을 실시했을 때의 결과이다. 시간복잡도를 생각했을 때

• 입력된 리스트의 요소를 합치므로 길이가 1이 될때 까지 수행한다. O(N)
• 반복을 수행하는 내부에서 정렬을 실시하므로 최종 O(N*NlogN) 소요

O(N)보다는 시간이 많이 소요되고 O(N^2)보다는 적은 시간이 소요되는 것을 볼 수 있다.
여기서 시간을 더 줄여야한다. 어떻게 줄여야할까?

옳은 접근

카드 묶음을 최소 힙트리로 구성하고, 힙트리의 루트노드를 pop하여 비교횟수를 계산한다.

해당 방법을 실시했을 때의 결과이다. 시간복잡도를 계산한다면
힙트리의 삽입/삭제의 시간복잡도를 생각하면 된다.
힙트리의 삽입은 트리구조로 구성하기 때문에 일반적으로 O(logN)이 소요된다.
힙트리의 삭제는 루트노드를 pop하기 때문에 O(1)이 소요되나, 트리를 재구성하기때문에 일반적으로 O(logN)이 소요된다.

결론

힙트리를 사용하지 않을 때 O(N*NlogN)이 소요되고,

힙을 이용할 때는 O(logN)선에서 처리되는 것을 볼 수 있다.

소스코드

import sys, heapq
from collections import deque
N = int(sys.stdin.readline())
card_arr = []
result = 0

if N == 1:
    print(0)
else:
    for i in range(N):
        heapq.heappush(card_arr,int(sys.stdin.readline()))

    while True:
        A = heapq.heappop(card_arr)
        B = heapq.heappop(card_arr)
        result += A
        result += B
        heapq.heappush(card_arr,A+B)
        if len(card_arr) == 1:
            break;

    print(result)