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

문제 링크

https://www.acmicpc.net/problem/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) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

 

출력

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

 

접근법

간단한 그리디 알고리즘 문제를 풀어보고 싶어서, 백준에서 알고리즘 분류로 찾아 들어와서 푼 문제인데

그리디 알고리즘이라고 하기에도 조금 민망한 간단한 문제였다.

 

그렇다고 해서 내가 사용한 알고리즘이 정확히 왜 되냐? 라고 수식으로 증명하기에는 실력이 부족해서 못하기는 한데

다음과 같은 접근법으로 이 문제를 풀었다.

 

일단 직관적으로 생각해보면, 문제의 예시처럼 크기가 10, 20, 40인 덱이 있을 때

가장 작은 크기의 덱 2개인 10, 20 크기의 덱을 먼저 합치는 것이 비교 횟수가 가장 적을 것 처럼 보인다.

왜냐하면 10, 20 크기의 덱을 합치면 30 크기의 덱이 되고, 여기서 이 30 크기의 덱을 다시 40 크기의 덱과 합쳐줘야 하는데

이 30이라는 숫자가 10, 20 크기의 덱을 합칠 때 비교 횟수이고, 두 번째로 40 크기의 덱과 합칠 때 (30 + 40)의 비교 횟수에서 한번 더 등장하기 때문이다.

 

즉 덱을 합치면 덱 크기가 커지는데, 이 커진 덱 크기가 이후의 비교 횟수에 계속해서 더해지기 때문에

작은 크기의 덱 끼리  먼저 합치면 뭔가 정답이 나올 것 같다는 느낌이 든다.

다른 예시를 한번 살펴보자.

 

각각 크기가 a, b, c, d인 4개의 덱이 있다고 하자. 어차피 a, b, c, d는 임의의 숫자이기 때문에 대충 알파벳 순서대로 문제에서 요구하는 것처럼 이 덱들을 하나로 합쳐보자.

입력: a b c d
단계 1: [ab] c d => 비교 횟수 (a + b)
단계 2: [abc] d => 비교 횟수 ((a + b) + c) 
단계 3: [abcd] => 비교 횟수 (((a + b) + c) + d)

위처럼 3번 덱을 합쳐서 4개의 덱을 하나로 합쳤을 때, 총 비교 횟수는

(a + b) + ((a + b) + c) + (((a + b) + c)) + d) = 3a + 3b + 2c + d

 

위 과정을 살펴보면 a와 b를 가장 처음에 합쳤기 때문에, 수식의 모든 항에 (a+b)가 전부 들어가 있다는 것을 알 수 있다.

즉 먼저 합쳐진 a와 b의 크기를 가장 작게 만들었을 때, 비교 횟수가 최솟값이 된다는 것이다.

 

마찬가지로 두 번째로 합쳐진 c도 d보다 작은 크기여야 한다는 것을 알 수 있다.

 

따라서 이 문제는 그리디하게 접근해서

덱이 전부 합쳐져서 하나가 될 때 까지, 가장 작은 크기의 덱 두개를 골라서 합치는 과정을 반복하면 되는 것이다.

여기서 주의할 점은 "가장 작은 크기의 덱"은 앞에서 이미 합쳐졌던 덱도 포함한다는 것이다.

 

코드로 구현할 때는 가장 작은 크기의 덱 2개를 항상 알아내야 하므로,

최적화를 위해 반복적으로 정렬하는 과정을 따로 하지 않고 PriorityQueue를 이용해서 구현했다.

 

받은 입력을 PQ에 전부 넣고,

가장 작은 크기 덱을 두개 선택해서 합친다음 그 비교 횟수를 누적해주고, 합친 덱의 크기를 다시 PQ에 넣어주는 과정을

덱이 하나 남을 때 까지 반복했다.

 

 

시간 복잡도

N개의 입력으로 PQ를 만드는 데 O(NlogN)의 시간 복잡도가 걸린다.

 

실제 알고리즘 동작 시에는 덱 2개를 PQ에서 뽑고 다시 PQ에 덱 1개를 집어 넣는 과정을 반복한다.

PQ에서 덱을 뽑거나 넣을 때 O(logN)의 시간 복잡도가 필요하므로, 덱이 한개 남을 때 까지 이 과정을 반복한다고 하면

O(NlogN) + O((N-1)logN) + O((N - 2)logN) + ... + O(logN)  

대충 이런 식의 시간 복잡도가 필요할 것이다.

 

N 부터 1 까지의 합은 N*(N-1)/2 이므로

전체 알고리즘의 시간 복잡도는 O(N^2 logN)이다.

 

공간 복잡도

N * 4 bytes.

PQ에 들어갈 입력에 대한 메모리.

처음엔 long으로 만들었는데, 돌려보니까 int로도 돌아간다.

 

 

풀면서 놓쳤던 점

딱히 없다.

 

 

이 문제에서 얻어갈 점

그리디 알고리즘 접근법.

 

 

코드

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

public class Main
{
    public static void main(String[] args) throws IOException
    {
        //N개의 카드 덱 사이즈를 읽어서 PriorityQueue에 넣는다 (오름차순 정렬)
        PriorityQueue<Integer> pq = readSizeOfDecks();

        int compareCnt = 0; //총 비교 횟수
        int deck1, deck2;

        //PQ에 덱이 하나 남을 때 까지 반복한다
        while (pq.size() > 1)
        {
            //PQ에서 덱 두개를 뽑는다
            deck1 = pq.poll();
            deck2 = pq.poll();

            //두 덱을 합친다.
            //합치면서 비교를 해야하므로 비교를 해야 하므로 비교 횟수를 누적시켜주고
            //덱이 한 개만 남을 때 까지 계속 합쳐야하므로 합친 덱을 다시 PQ에 넣는다.
            compareCnt += deck1 + deck2;
            pq.add(deck1 + deck2);
        }

        //누적된 비교 횟수 출력
        System.out.println(compareCnt);
    }

    static PriorityQueue<Integer> readSizeOfDecks() throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //덱 개수 입력
        int numOfDecks;
        numOfDecks = Integer.parseInt(br.readLine());

        //반환할 PriorityQueue
        PriorityQueue<Integer> pq = new PriorityQueue<>(numOfDecks);

        //덱의 크기를 입력받아서 PQ에 넣는다. 오름차순 정렬된다.
        for (int i = 0; i < numOfDecks; i++)
            pq.add(Integer.parseInt(br.readLine()));

        return pq;
    }
}