백준 1715번 : 카드 정렬하기 java

이 문제는 허프만 알고리즘을 이용하는 간단한 문제입니다.

허프만 알고리즘에 대한 설명은 아래의 글에 있습니다.

백준 13975번 : 파일 합치기 3 java

---

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

        Queue<Integer> q = new PriorityQueue<>();
        for(int i = 0; i<N; i++)
            q.offer(Integer.parseInt(br.readLine()));

        int sum = 0;

        if(N == 1){
            System.out.println(0);
            return;
        }

        while(true){
            int a = q.poll();
            int b = q.poll();

            sum += a+b;

            if(q.isEmpty())
                break;

            q.offer(a+b);
        }

        System.out.println(sum);
    }
}

허프만 알고리즘에 대해 알고 있다면 쉽게 풀 수 있는 문제였습니다.