[baekjoon] 백준 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) 

- 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

알고리즘

- 위 문제는 카드 묶음에서 제일 작은 2개의 덱을 더해주고 다시 그 덱을 카드 묶음에 넣어 또다시 제일 작은 2개의 덱을 더해주어 푸는 문제로 힙큐를 사용하면 된다. 

- 카드 묶음의 수를 입력받는다.

- 반복문을 통해 카드 묶음의 크기를 입력받는다. 이때, 힙큐를 통해 리스트에 넣는다.

- 카드 묶음이 하나이면 비교할 필요가 없기 때문에 0을 출력한다.

- 힙팝을 통해 카드에서 제일 작은 2개의 덱을 출력시켜 더해준다.

- 더해준 카드를 다시 카드 묶음에 넣어 위와 같이 다시 제일 작은 2개의 덱을 출력시켜 더해준다.

- 위 과정을 반복할 때 현재 비교 횟수를 더해준다. 

코드

import sys
import heapq

n = int(input())
result = 0
card = []

# 카드 묶음의 크기를 힙큐를 통해 card 리스트에 넣는다.
for _ in range(n):
    heapq.heappush(card,int(sys.stdin.readline()))

# 카드 묶음이 하나이면 비교할 필요가 없기때문에 0을 출력한다.
if n == 1:
    print(0)
else:
    # 카드 묶음이 1보다 클때까지 반복한다.
    while len(card) > 1:
        temp_1 = heapq.heappop(card)  # 제일 작은 덱
        temp_2 = heapq.heappop(card)  # 두번째로 작은 덱
        result += temp_1 + temp_2  # 현재 비교 횟수를 더해줌
        heapq.heappush(card, temp_1 + temp_2)  # 더한 덱을 다시 넣어줌

    print(result)

결과

위 코드에서 while문 밑에 print(card)를 작성하게 되면 힙큐를 통해 카드 묶음에서 제일 작은 2개의 덱이 더해지고 다시 카드 묶음에 들어간 것을 출력 화면과 같이 확인할 수 있다.

<출력화면>

위 출력 화면을 보게 되면 10, 20, 40의 카드 묶음의 크기가 들어간 카드 묶음을 볼 수 있고 카드 묶음에서 제일 작은 2개의 덱인 10과 20을 힙큐를 통해 나오게 하고 나온 두 개의 값을 더한 30이 다시 카드 묶음에 들어가게 하여 카드 묶음 안에 30과 40이 있는 것을 확인할 수 있다. 그리고 현재 비교 횟수를 계속해서 더해주어 총 몇 번의 비교를 했는지 출력하면 된다.

따라서 코드를 분석하게 되면 힙큐를 통해 카드 묶음에서 제일 작은 2개의 덱을 나오게 한 후에 2개의 덱을 더한 카드를 다시 카드 묶음에 넣어 위 같은 과정을 반복하면 된다. 그리고 그때마다 비교한 횟수를 변수에 더해주어 최종적으로 비교 횟수를 출력하면 된다.

github

junjange/CodingTest