[BOJ] 1715 : 카드 정렬하기(Java)

문제

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

 

출력

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

---

💡 풀이

❌ 잘못된 시도 방법

문제를 처음 봤을 때 들었던 생각은 단순하게 오름차순으로 정렬해서 다음과 같은 일반화된 식으로 접근하면 되지 않을까? 라고 생각하여 문제를 풀었다. 

정렬된 카드 묶음들의 수를 각각 $a_i, a_{i+1}, a_{i+2} ... a_{i+(N-1)}$ 이라 했을 때,

잘못된 방식입니다..

와 같은 식이 나왔다. 그래서 이를 그대로 적용했더니 당연히 "틀렸습니다"라는 결과가 나왔다.. 

그래서 반례를 생각해봤다. 

하나의 반례를 살펴보면 입력값이 4 30 30 40 50 인 경우이다. 
위와 같은 (잘못된)논리로 풀이를 해보면, 우선 오름차순 정렬하여 30 30 40 50일 것이고, 차례로 합을 더해가면 값이 310이 나온다. 하지만 정답은 300이다. 30과 30을 묶고 40과 50을 묶은 뒤, 이 둘을 묶으면 결국 30+30=60, 40+50=90, 60+90=150이므로 60, 90, 150을 더하면 300이 나오게 되는 것이다. 이 반례를 통해, 오름차순으로 정렬하되, 두 카드 묶음을 더할 때마다 계속 오름차순으로 정렬해줘야 한다는 것을 깨닳았다. 

 

그래서 이를 구현하기 위해 while문을 돌며 반복문을 돌 때마다 정렬을 시켜줬더니 시간초과가 발생하더라.. 

⭕ 올바른 풀이

이를 정말로 해결하기 위해 "우선순위 큐"를 사용했다. 값이 들어갈 때마다 오름차순으로 정렬이 되어 들어가기 때문에 반복문마다 시행되는 정렬의 시간을 줄일 수 있었다. 

그리고 입력값의 조건을 보면 1<=N 이기 때문에 카드 묶음이 하나만 들어오면, 최소 비교 횟수는 0번인 것을 주의하자! 

 

전체적인 코드는 다음과 같다. 

import java.util.*;

public class Q1715 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        // 카드 묶음이 1개라면 비교 횟수가 0번이다.
        if (N == 1) {
            System.out.println(0);
            return;
        }

        // 카드 묶음을 오름차순으로 정렬하기 위해 우선순위 큐를 사용
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            pq.offer(sc.nextInt());
        }

        int result = 0;
        while (pq.size() > 2) {
            // 카드 묶음의 수가 가장 적은 두 묶음을 합친다. 
            int num1 = pq.poll();
            int num2 = pq.poll();
            result += num1 + num2;

            // 이 합친 카드 묶음을 다음 카드 묶음들과 합치기위해 다시 우선순위 큐에 넣어준다. 
            pq.offer(num1 + num2);

        }

        // 우선순위 큐에 남아있는 원소들 모두 더해주기
        while (!pq.isEmpty()) {
            result += pq.poll();
        }

        System.out.println(result);

    }
}