[백준] 1715. 카드 정렬하기 (python)

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

1715번: 카드 정렬하기

 

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

풀이

여러 개의 카드 묶음이 주어졌을 때 무슨 순서로 합쳐야 비교 횟수가 최소가 될지 알아야 한다.

비교를 최소로 하려면 해당 묶음 중에서 가장 작은 두개의 카드를 합친 뒤에, 합친 카드 묶음을 더해

그 중에서 다시 가장 작은 두 개의 카드를 합친다.

이런 식으로 반복해서 하나의 카드 묶음이 될 때까지 더하면 된다.

 

처음에는 리스트에 카드 묶음 수를 넣어서 정렬하고, 가장 앞의 두개를 차례로 더해서 누적합을 구해줬는데, 

새롭게 합친 카드 묶음이 생길 때마다 정렬을 다시 해줘야 한다.

근데 리스트 정렬은 O(NlogN)이고, 매번 정렬을 해주면 N*NlogN인데

입력 최대 수가 10만이기 때문에 이럴 경우 시간 초과가 나게 된다.

 

따라서 이 문제는 '우선순위 큐'를 이용하는 게 관건인 것 같다.

파이썬에서 제공하는 heapq는 '최소힙'이 디폴트이므로 이 문제에서는 따로 정렬기준을 바꿀 필요는 없다.

heapq는 삽입과 삭제가 O(logN)의 시간복잡도를 가지고,

삽입과 동시에 정렬이 되기 때문에, 새로운 카드 묶음을 추가할 때 따로 정렬을 해주지 않아도 된다.

 

import sys
import heapq
input = sys.stdin.readline
n = int(input())
heap = []
for _ in range(n):
    heapq.heappush(heap, int(input()))

sum = 0
while len(heap) > 1:
    a = heapq.heappop(heap)
    b = heapq.heappop(heap)
    sum += (a+b)
    heapq.heappush(heap,a+b)

print(sum)

 

내가 헷갈렸던 부분이 또 하나 있는데 바로 N이 1일 경우이다.

N이 1 이고 한 개의 카드 묶음의 개수가 주어지면

출력값으로 해당 카드 묶음 수를 출력하면 된다고 생각했다.

 

그래서 N이 1일 경우의 조건문을 따로 빼서 하나 입력되어 있는 카드수를 출력해줬는데, 틀렸다.

문제 설명의 첫 문장을 보면

정렬된 두 묶음의 숫자 카드가 있다고 하자. 

라고 적혀있기 때문에 하나의 카드 묶음만 들어온다면 이미 정렬되어 있으므로 비교할 필요가 없다.

즉, 0이 출력되어야 한다.

 

우선순위 큐를 배우긴 했었지만, 제대로 문제에 사용해본 적이 없어서

이 문제를 봤을 때 우선순위 큐를 떠올리지 못했다.

근데 이 문제를 풀어보니 우선순위 큐가 확실히 효율적인 자료구조인 걸 깨달았다.

나중에 우선순위 큐 개념과 시간복잡도 등에 대해 공부한 포스팅도 올려야겠다.

 

알고리즘 분류

• 우선순위 큐
• 정렬