[JAVA] 백준 1715번 카드 정렬하기

문제

1715번: 카드 정렬하기

입력

• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

• 첫째 줄에 최소 비교 횟수를 출력한다.

입력 예제

3
10
20
40

출력 예제

100

문제 풀이

• 가장 작은 값 두개를 계속해서 더해나가면  최소 비교횟수를 도출해낼 수 있다.
• pq에 입력받은 값을 모두 넣은 후, 값이 2개 이상 있다면, 임시적으로 값을 더한다.
• 임시적으로 더한 값을 최종 값에 더해준 후, pq에 다시 넣는다.
• 위 과정을 반복한 후, pq의 size가 1이 된다면 최종 값을 출력한다.

코드

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class boj1715 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(arr);
//		print(arr, n);

		
		// pq에 배열 값들 복사
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		for (int i = 0; i < n; i++) {
			pq.add(arr[i]);
		}
		
		int sum = 0;
		while (pq.size() >= 2) {
			int tmp = pq.poll() + pq.poll();
			sum += tmp;
			pq.add(tmp);
		}
		System.out.println(sum);
	}

	private static void print(int[] arr, int n) {
		for (int i = 0; i < n; i++) {
			System.out.println(arr[i]);
		}
	}

}