백준 1260번: 카드 정렬하기

 

문제 풀이

1. 우선순위 큐 (Priority Queue): 우선순위 큐를 사용하면, 가장 작은 두 묶음을 빠르게 꺼낼 수 있습니다. 자바에서는 PriorityQueue 클래스를 사용하여 이를 구현할 수 있습니다.
2. 그리디 알고리즘: 가장 작은 두 묶음을 합친 후, 그 결과를 다시 큐에 넣고, 이 과정을 반복하여 최소 비교 횟수를 구합니다.

 

해결 방법

1. 먼저, 카드 묶음의 크기들을 우선순위 큐에 넣습니다.
2. 큐에서 가장 작은 두 묶음을 꺼내 합칩니다. 이때, 합치는 과정에서 비교 횟수가 추가됩니다.
3. 합친 묶음의 크기를 다시 큐에 넣고, 이 과정을 반복합니다.
4. 큐에 카드 묶음이 하나만 남을 때까지 이 과정을 반복하며, 비교 횟수를 계속 더해갑니다.

 

자바 코드 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 카드 묶음의 수 N
        int N = sc.nextInt();
        
        // 우선순위 큐 (최소 힙)
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 카드 묶음의 크기 입력
        for (int i = 0; i < N; i++) {
            pq.offer(sc.nextInt());
        }
        
        int totalComparisons = 0;
        
        // 두 묶음을 합치는 작업을 반복
        while (pq.size() > 1) {
            // 가장 작은 두 묶음을 꺼냄
            int first = pq.poll();
            int second = pq.poll();
            
            // 두 묶음을 합친 비교 횟수
            int sum = first + second;
            totalComparisons += sum;
            
            // 합친 묶음을 다시 우선순위 큐에 넣음
            pq.offer(sum);
        }
        
        // 결과 출력
        System.out.println(totalComparisons);
        
        sc.close();
    }
}

 

 

시간 복잡도

• 우선순위 큐에서 poll()과 offer()는 각각 O(log N) 시간이 걸립니다.
• 이 작업을 카드 묶음 수 N에 대해 반복하므로, 전체 시간 복잡도는 O(N log N)입니다.
• 따라서, 주어진 문제의 최대 크기인 N = 100,000에 대해서도 충분히 효율적으로 해결 가능합니다.