[JAVA] 백준 1715번 【G4.카드 정렬하기】

문제

1715번: 카드 정렬하기

 

풀이

1️⃣ PriorityQueue 를 활용한 풀이

💡 떠오른 Idea

약간, 그리디 처럼 생각을 해보았다.

누적으로 묶음의 수만큼 합쳐지므로, 가장 작은 묶음의 수만 중복으로 값에 더해져야한다.

결론은, 카드 묶음을 합치는데 남은 카드 묶음 중에서 가장 작은 두 묶음을 골라서 합쳐야 한다.

카드 묶음을 합치게 되면, 다른 후보 묶음들 보다 커지게 될 수도 있고 여전히 작을 수도 있다.

따라서, 일단은 이 카드 묶음을 다시 후보로 올려두고, 남은 후보들 중 다시 가장 작은 카드 묶음 2개를 선택해서 합쳐야한다.

이러한 방식을 후보로 남아있는 카드 묶음이 1개가 될때까지 반복해야한다.

계속해서 작은 카드 묶음을 사용하기 위해 우선순위큐를 활용하면 O(logN)의 시간복잡도로 값들을 정렬하기 때문에 효율적으로 해결할 수 있다.

 

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

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<>();

        while (N-- > 0) {
            pq.add(Integer.parseInt(br.readLine()));
        }

        int result = 0;

        while (true) {
            if (pq.size() <= 1) {
                break;
            }
            int A = pq.poll();
            int B = pq.poll();
            int sum = A + B;
            result += sum;
            pq.add(sum);
        }
        
        System.out.println(result);
    }
}

 

📖 회고

우선 순위 큐의 원리를 잘 파악하면 쉽게 풀 수 있는 문제였다.

 

문제가 조금 이해하기 어렵게 쓰여있어서, 단순하게 계속 작은 카드 묶음 2개를 골라서 합친다 라고 단순화했더니 쉽게 해결할 수 있었던 것 같다.

 

문제의 핵심을 빠르게 파악하는게 중요한 것 같다.