코드트리 [자바 java] 숫자 합치기

https://www.codetree.ai/missions/8/problems/%08merge-numbers?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

숫자 합치기 문제는 배열이 주어졌을 때 숫자를 두개씩 합쳐서 하나의 수를 만드는 것입니다. 이 때 a라는 숫자와 b라는 숫자를 합칠 때 필요한 비용은 a+b라고 할 때 가능한 최솟값을 구해야 한다고 합시다.

 

배열이 1, 3, 8, 10 일때는 오름차순으로 정렬하고 앞에서부터 차례로 더해나가면 되지만, 50,50,50,50,일 때에는 앞에서부터 차례로 더하면 450이 되고, 앞에 두개 뒤에 두개 더하고 합치면 400으로 더 작은 방법이 존재한다. 

 

이처럼 예외 없이 최솟값을 구하려면, 수를 한 번 더할 때마다 정렬하면 된다.

 

나는 이 문제를 풀 때 priorityQueue를 사용하였다.

 

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


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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr= new int[n];
        
         PriorityQueue<Integer> q = new PriorityQueue<>();

        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            q.add(arr[i]);
        }

        int ans = 0;

       

        while(q.size() != 1){
            int a = q.poll();
            int b = q.poll();
             //System.out.println(a);
            ans += (a+b);

            q.offer(a+b);

        }

        System.out.println(ans);

       


    }
}