[백준] 1715번: 카드 정렬하기(자바)

➰문제

 

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

 

예제 입력 1 

3
10
20
40

 

예제 출력 1 

100

 

 

 

1715번: 카드 정렬하기

 

---

 

💡풀이

 이 문제는 그리디 알고리즘을 적용한 문제다.

우선 순위 큐를 사용해야 함.

 

1. 각 카드 묶음 수를 입력받으며 우선 순위 큐( pq )에 저장한다.

   (아무런 설정도 하지 않으면 낮은 숫자 순으로 우선순위가 결정된다.)

 

2. pq의 맨 위의 값을 꺼내고, 한 번 더 꺼내어 더해서 tmp 변수에 저장한다.

   (두 번 연속으로 꺼내면 값이 작은 순서대로 두 개의 수가 꺼내어진다.)

 

3. 두 묶음을 비교한 횟수 tmp를 최종 횟수를 출력할 변수 sum에 더한다.

 

4. 다음 비교 횟수는 이전의 비교 횟수와 더한 값이므로 tmp 값을 pq에 추가한다.

   (추가하면 자동으로 우선 순위를 결정하여 정렬 된다.)

 

5. 비교할 값이 하나만 남을 때까지 반복한다.

 

 

 

⭐제출 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();     //카드 묶음 수
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0; i<N; i++){
            pq.add(scan.nextInt());     //낮은 숫자 순으로 우선순위 결정
        }

        int sum = 0;
        while(pq.size() > 1){       //비교할 값이 하나만 남을때까지
            int tmp = pq.poll() + pq.poll();
            sum += tmp;  //작은 수 두 개를 더해서 다시 큐에 추가
            pq.add(tmp);
        }
        System.out.println(sum);
    }
}