[BOJ 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보다 작거나 같은 양의 정수이다.

 

출력

---

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

 

예제 입력

---

3             |         100
10           |
20           |
40           |

 

 

처음에는 사실 정렬한 후에, 앞에서부터 차례로 쭉 더하면 되지 않을까??였다.

그래서 구현한 결과는??

출력초과...

너무 큰값이 나오는 문제였다.

사실상 '틀렸습니다'와 다르지 않은 결과였다.

 

카드 묶음의 관점에서 다시 생각해보니,

카드 묶음이 10 20 21 22 23 35 라고 생각했을 때 하나하나 생각해보면,

1. 10 + 20 을 통해 30개의 카드 묶음이 생긴다.
2. 21 22 23 30 35 순서의 정렬된 카드 묶음이 생긴다.
3. 21 + 22 를 통해 43개의 카드 묶음이 생긴다.
4.  ...

즉, 앞에 두묶음을 더한 새로운 카드 묶음이 생긴다고 생각하여야한다.

 

자세한 이해는 코드!!

 

import heapq
import sys

N = int(sys.stdin.readline().rstrip())

hq = []
answer = 0

for _ in range(0,N):
    heapq.heappush(hq,int(sys.stdin.readline().rstrip()))

if N == 1:
    answer = 0
else:
    for _ in range(0,N-1):
        a = heapq.heappop(hq)
        b = heapq.heappop(hq)
        answer = answer + a + b
        heapq.heappush(hq,a+b)

print(answer)

 

처음에 생각을 잘해야하는 문제이다.

또 정렬을 매반복문마다 하는 순간 N^2 logN이 되어 버리고 N의 범위가 100,000 이므로 NlogN의 시간 복잡도 내에 해결해야한다.

즉, 매번 삽입할때마다 logN의 시간으로 자동 정렬되는 heapq를 통해서 구현해야하는 문제였다. 

N의 범위에 따른 시간복잡도는 다음을 참고하면 좋을 것 같다😁