[Java] 백준_카드 정렬하기_1715

문제1

 

풀이

여러 묶음 중 어떤 2가지 묶음을 선택하느냐에 따라 전체 비교 횟수가 달라진다. 문제의 예시만 봐도 알 수 있다.

예시를 보면 작은 묶음을 먼저 선택하는게 비교 횟수가 적어지는 것을 알 수 있다.

따라서 전체 묶음에서 가장 작은 2가지 묶음을 선택해서 비교 횟수를 추가한 뒤에

다시 합쳐진 묶음을 전체 묶음에 추가하고 정렬을 해줘야 한다. 

묶음을 추가하고 정렬을 해야되는 구조가 우선순위큐와 비슷한 구조이고 우선순위의 경우 삽입 삭제가 O(logN)이므로 빈번하게 삽입삭제가 나타나는 이 문제에서 사용하기 적절하다.

 

소스코드

package 백준;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
 
/*
* N개의 숫자 카드 묶음의 크기가 각각 주어질 때, 최소한 몇 번의 비교가 필요한지 구하는 프로그램을 작성하세요.
* 비교 횟수의 최솟값을 구해야하는 문제.
* 핵심:여러 묶음 중 가장 값이 작은 그룹 먼저 연산 횟수를 더해야 최소 비교 횟수를 구할 수 있다.
*
* PriorityQueue이용
* 2개 꺼냄
*
* while(q.size() >1)
* sum = a1 + a2;
* answer += sum;
* q.add(sum);
*
* */
public class 카드정렬하기_1715 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());    // 카드 갯수 입력
 
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i=0; i<N; i++) {
            q.add(Integer.parseInt(br.readLine())); // 카드 값 입력
        }
 
        int sum =0;
        int num1, num2;
        while (q.size() != 1) {
            num1 = q.poll();
            num2 = q.poll();
            sum += num1 + num2;
            q.add(num1 + num2);
        }
 
        System.out.println(sum);
    }
}