[Algorithm] 카드 정렬하기

문제

정렬된 두 묶음의 숫자 카드가 있을 때, 각 묶음의 카드의 수를 A, B라고 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B번 비교를 해야 한다.

매우 많은 숫자 카드 묶음이 책상 위에 있다. 이들을 두 묶음씩 골라 서로 합쳐나가면 고르는 순서에 따라서 비교 회수가 달라진다. N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지 구하는 프로그램을 작성하시오.

 

풀이

먼저 각 묶음마다 몇개 인지 적힌 배열을 정렬했다.

그리고 앞에서부터 합하면서 계산했다.

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Integer[] arr = new Integer[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        Arrays.sort(arr);

        int sum = arr[0] + arr[1];
        
        for (int i = 2; i < n ; i++) {
            sum += sum + arr[i];
        }
        

        System.out.println(sum);
    }
        
}

처음 생각한 방식은 정렬된 상태로 계속 더하면 최소가 될 것이라 생각했는데, 합한 값이 기존의 카드 묶음들의 개수보다 커지면 더 이상 최소가 아닌 상황이 되어버렸다. 차라리 우선순위 큐를 활용해 계속 큐에 작은 값이 앞으로 와서 비교 횟수를 최소화 하는 것이 좋았다.

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            pq.offer(sc.nextInt());
        }
        int sum = 0;
        while (pq.size() != 1) {
            int first = pq.poll();
            int second = pq.poll();
            int tmp = first + second;
            sum += tmp;
            pq.offer(tmp);
        }
        

        System.out.println(sum);
    }
        
}

위와 같이 우선순위 큐는 합한 결과를 넣어줘도 카드 묶음이 작은 것부터 먼저 비교하게 되어있다.