[JAVA][Baekjoon] 1715번 카드 정렬하기🌟🌟

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

 

📌 접근 방식

이 문제는 우선순위 큐(Priority Queue)를 활용한 그리디 알고리즘을 적용해야 하는 문제! 🎯

1️⃣ 최소 비교를 위해 가장 작은 두 카드 묶음을 계속 합치는 것이 핵심이다. 가장 작은 두 묶음을 먼저 합쳐야 이후의 비교 횟수를 최소화할 수 있다.
2️⃣ 카드 묶음을 최소 힙(Min Heap)에 저장하면, 가장 작은 두 값을 쉽게 추출할 수 있다. 힙에서 두 묶음을 꺼내 합치고, 합친 묶음을 다시 힙에 넣는 과정을 반복한다.
3️⃣ 이 과정을 카드 묶음이 하나만 남을 때까지 반복한다. 🎉

[알고리즘] 그리디 알고리즘(Greedy Algorithm)

 

✅ PASS CODE

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int i = 0; i < N; i++) {
            pq.add(Integer.parseInt(br.readLine())); // 카드 묶음을 우선순위 큐에 저장
        }

        int totalComparisons = 0; // 총 비교 횟수
        while (pq.size() > 1) {
            int first = pq.poll(); // 가장 작은 묶음
            int second = pq.poll(); // 두 번째로 작은 묶음
            int sum = first + second; // 두 묶음을 합침
            totalComparisons += sum; // 비교 횟수 추가
            pq.add(sum); // 합친 묶음을 다시 큐에 추가
        }

        System.out.println(totalComparisons);
    }
}

💡 코드 설명

1. PriorityQueue 사용: 우선순위 큐는 최소 힙을 구현. ➡️ 항상 가장 작은 값을 효율적으로 꺼낼 수 있다.
2. 카드 묶음 추가: 입력받은 카드 묶음을 모두 큐에 추가한다.
3. 반복 합치기: 큐의 크기가 1이 될 때까지 두 묶음을 꺼내 합치고, 비교 횟수를 더한다. 합친 묶음은 다시 큐에 넣는다.
4. 결과 출력: 총 비교 횟수를 출력한다.

😊 느낀 점

처음에는 단순히 작은 카드 묶음부터 합치면 된다고 생각해서 일반 배열을 사용해 정렬하여 누적합으로 구하는 방법을 떠올렸다. 하지만 누적합으로 구하는 방식은 작은 묶음을 효율적으로 추출하기 어렵고, 시간이 오래 걸린다는 단점이 있었다.
입력 크기(N)가 최대 100,000이기 때문에, O(N log N)의 성능을 가진 힙 자료구조를 사용하는 것이 적합했다. 우선순위 큐를 활용해 가장 작은 두 값을 효율적으로 추출하니, 시간 복잡도를 최소화하며 문제를 해결할 수 있었다.

이번 문제를 통해 그리디 알고리즘이 최적의 해를 보장하는 조건을 더 명확히 이해할 수 있었다. 앞으로 비슷한 문제를 여러 번 풀어보면서 개념을 더욱 확실히 다져야겠다! 😊