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

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

정렬된 카드 묶음들을 합칠 때 어떤 방식으로 합쳐야 비교를 최소한 할 수 있는지 묻는 문제이다.

문제를 푸는데는 상관이 없지만 문제에서 20장의 카드와 30장의 카드를 합치려면 20 + 30 = 50 번의 비교가 필요하다고 했다.

카드 수를 적게 하여 예시를 들어보면 어렵지 않게 이해할 수 있을 것이다.

e.g. A = [1, 2, 6], B = [3, 4, 8]을 합친다고 가정

1, 3 비교 => [1, ]
2, 3 비교 => [1, 2, ]
6, 3 비교 => [1, 2, 3, ]
6, 4 비교 => [1, 2, 3, 4, ]
6, 8 비교 => [1, 2, 3, 4, 6, ]
A 묶음의 카드 모두 소진됨!

이미 정렬되어 있다고 가정하였으므로, B의 남은 카드는 모두 뒤에 추가함

※ 따라서 합친 카드는 [1, 2, 3, 4, 6, 8] 이며, 총 3 + 3 = 6 번의 비교가 필요

이제 문제를 생각해보자. 우리는 비교를 최소한 진행해야 하므로 가장 작은 개수의 카드 묶음들부터 뽑아서 합쳐야 한다.

그러면 우선순위 큐를 사용하여 아래와 같이 생각해 볼 수 있다. 값은 예제 입력을 기준으로 설정하였다.

1. 10, 20, 40을 우선순위 큐에 넣고 오름차순 정렬

2. 가장 작은 숫자 2개를 pop
   => 10 pop, 20 pop 한 다음 더한 결과 30을 다시 우선순위 큐에 push
   => answer에 따로 저장 (answer += 10 + 20 = 30)

3. 가장 작은 숫자 2개를 pop
   => 30 pop, 40 pop 한 다음 더한 결과 70을 push
   => answer에 따로 저장 (answer += 30 + 40 = 70)

   우리가 구하고자 하는 answer = 100이 됨

2, 3번 과정을 우선순위 큐의 크기가 1개 남을 때까지, 다시 말해 더 이상 비교할 묶음이 없을 때까지 반복하면 된다.

따라서 전체 소스코드는 다음과 같다.

import java.util.*;
import java.io.*;

public class P_1715 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            queue.offer(Integer.parseInt(br.readLine()));
        }

        int answer = 0;
        while (queue.size() > 1) {
            int first = queue.poll();
            int second = queue.poll();

            int result = first + second;
            answer += result;

            queue.offer(result);
        }

        System.out.println(answer);
    }
}