BOJ 1715번 : 카드 정렬하기 (Python/Gold 4)

1715번: 카드 정렬하기

---

설명

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

예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

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

 

풀이

● 테스트 케이스 - 4 40 100 20 120 / 결과 500

4개의 카드 묶음이 정렬되지 않은 채로 있다. 비교한 횟수가 최소가 되어야 하므로 가장 작은 묶음부터 비교한다.

 

1. 20 vs 40 → 20과 40을 비교했으므로 20 + 40 = 60, 비교횟수는 60이다. (편하게 묶음으로 봐도 된다.) 

그럼 남은 묶음들은 60 100 120이다. 세 묶음들 중 가장 작은 것은 60과 100이다. 이 둘을 비교한다.

2. 60 vs 100 → 60 + 100 = 160, 비교횟수는 160이다. 남은 묶음들은 160 120이다. 두 묶음뿐이니 둘을 비교한다.

3. 160 vs 120 → 160 + 120 = 280, 비교횟수는 280이다. 비교할 묶음이 없으므로 지금까지 비교한 횟수를 더한다.

4. 60 + 160 + 280 = 500, 최소 비교 횟수는 500이다.

---

✓ 우선순위 큐 사용

 

1. 클래스 임포트

from queue import PriorityQueue

2. 우선순위 큐 생성

queue = PriorityQueue()
queue = PriorityQueue(maxmize = 10) #크기 지정

3. 우선순위 큐에 원소 추가

queue.put(n)

4. 우선순위 큐 원소 삭제

queue.get() #가장 작은 값이 반환된다.

5. 정렬 기준 변경((우선순위, 값))

queue.put((1, 5))

queue.get()[1] #5가 반환된다.

 

Solution

# 00:42 - 01:55 / 15:23 - 16:06

import sys
input = sys.stdin.readline

from queue import PriorityQueue #우선순위 큐 클래스(queue = 내장 모듈)
#우선순위 큐는 제거될 때 가장 작은 값을 제거한다. 정렬할 필요가 없겠죠?

n = int(input())
card = [] #카드 묶음을 담을 리스트
for _ in range(n):
    card.append(int(input())) 

q = PriorityQueue() #우선순위 큐 생성
#큐가 빌 때까지 반복
#1. 큐에 카드묶음을 모두 넣기
for i in card:
    q.put(i)
#2. 작은 묶음 두 개를 비교
res = 0 #출력할 결과
while q.qsize() > 1: #큐에 들어있는 값이 1일 때 더할 필요가 없으므로 한 개가 남을 때까지만 반복
    x = q.get() #큐에서 가장 작은 값을 제거하고 x에 저장
    sum = x + q.get() #두 묶음을 더한다.
    res += sum #더한 값을 결과에 저장한다.
    q.put(sum) #더한 값을 다시 큐에 넣는다.
print(res)

---

문제를 이해하는 데 많은 시간이 소요 됐다. 처음에는 주어진 예시로만 봐서는 이해가 간 줄 알았는데 다른 테스트 케이스들을 보니 이해한 거랑 전혀 다르게 나왔다. 가장 작은 더미랑 비교를 해야 하는데 그걸 무시하고 더해갖기 때문이다.  다른 사람한테도 물어보면서 풀려고 했는데 여전히 모르겠어서 포기하고 있다가 다시 풀었는데, 어느 한 분이 문제 설명을 잘 해주셔서 잘 이해했고 문제도 어렵지 않게 풀 수 있었다. 그래도 문제는 잘 풀어서 다행인 듯 싶다.