[백준] 카드 정렬하기

최동혁·2022년 12월 6일

백준

목록 보기

55/68

카드 정렬하기

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 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보다 작거나 같은 양의 정수이다.

출력

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

예제 입력 1

예제 출력 1

문제 해석

처음에 문제를 보고 잘못 해석해서 처음에 bisect 모듈을 이용한 bisect_left를 이용하여 풀이를 하였다. 하지만 간과한것이 bisect 모듈은 원소들이 정렬되어 있을때에만 정상 작동한다. 만약 정렬되어 있지 않고 섞여있다면 절대 쓰면 안됨.

카드들을 비교하는데 최소로 비교하는 횟수를 출력해야 한다.

여기서 실수한 것이, 30 40 50 60을 비교하는 것을 예로 들어보자

내가 생각한 방식은 (30 + 40) + (70 + 50) + (120 + 60) = 370이다.

그런데 30과 40을 비교하고 나서 70이 나왔으면 70보다 작은 수인 50과 60을 먼저 비교하고 후에 비교를 해야한다.

즉, (30 + 40) + (50 + 60) + (70 + 110) = 360이다.

입력받은 리스트들을 가장 최적의 시간으로 최소값을 뽑아내야 하는 알고리즘은 최소힙이 있다. 그리고 더한 결과도 힙에 넣어주면 알아서 최소값들을 뽑아내준다.

풀이

한줄씩 입력 받을 때마다 heappush를 해준다.
N - 1번 루프를 돌면서 가장 작은 수와, 그 다음 작은 수를 heappop해서 더한 후 다시 heappush를 해준다. 물론 push 하기 전에 더한 수를 ans라는 리스트에 넣어준다. 왜냐면 이것또한 더해줘야 하기 때문이다.
또 하나의 예외가 있는데 N이 만약 1이라면 비교할 필요가 없으니 0을 출력 해줘야한다.

import sys
import heapq

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

card = []



for i in range(N):
    heapq.heappush(card, int(sys.stdin.readline()))


ans = []


if N == 1:
    print(0)
    exit()

for i in range(N - 1):
    pop_1 = heapq.heappop(card)
    pop_2 = heapq.heappop(card)
    card_sum = pop_1 + pop_2
    ans.append(card_sum)
    heapq.heappush(card, card_sum)
print(sum(ans))