[자바/그리디] 코드트리. 숫자합치기

문제

링크

해석

숫자 리스트 중 매번 가장 최소의 숫자 두 개를 골라서 합치는 비용을 더해주면 되는 문제이다.

ArrayList를 이용해서 매번 정렬을 수행하며 숫자를 관리해도 되지만, 이 문제에 한해서는 힙을 사용하는 게 더 효율적이라 봐서 PriorityQueue를 적용해 풀었다.

코드

public class Main {
    /*
    * 수행시간 : 678 ms
    *
    * 메모리 : 27 MB
    *
    * 시간복잡도 : O(N * logN)
    * */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] arr = Stream.of(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int ans = solution(n, arr);

        bw.write(String.valueOf(ans));

        br.close();
        bw.flush();
        bw.close();
    }

    private static int solution(int n, int[] arr) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i : arr) {
            pq.add(i);
        }

        int ans = 0;
        while (pq.size() >= 2) {
            Integer a = pq.poll();
            Integer b = pq.poll();
            ans += (a + b);
            pq.add(a + b);
        }

        return ans;
    }
}