[이코테][Java] 카드 정렬하기

문제링크: https://www.acmicpc.net/problem/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
• N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기의 수

출력조건

• 최소 비교 횟수 출력

입출력 예시

• 입력예시	출력예시
  3 10 20 40	100

 

 

 

 

문제 풀이

생각한 풀이 방법 

→ 매번 주어진 N개의 숫자 카드 묶음 중에서 카드 개수가 작은 묶음 2개를 골라서 합치면 최소 비교 횟수를 구할 수 있다.

 

실패한 풀이

• N개의 숫자 카드 묶음을 int 배열 cards에 저장하고 오름차순 정렬한 후, 맨 앞의 카드 묶음부터 순서대로 합친다.
• 이 코드로 n=5, [1, 2, 3, 4, 5]인 경우를 수행하면
  → (1+2) + (3+3) + (6+4) + (10+5) = 34 번 비교가 필요하다.
       하지만 이 경우의 최소 비교 횟수는 (1+2) + (3+3) + (4+5) + (6+9) = 33 이다.
       실패한 코드는 처음 정렬한 순서 그대로 카드 묶음을 더했기 때문에 최소 비교 횟수를 구할 수 없다.

import java.io.*;
import java.util.Arrays;

public class Main1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[n];
        for (int i = 0; i < n; i++) {
            cards[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(cards);


        int sum = cards[0] + cards[1];
        int result = sum;
        for (int i = 2; i < n; i++) {
            result += sum + cards[i];
            sum += cards[i];
        }
        System.out.println(result);
    }
}

 

 

---

 

 

성공한 풀이(Priority Queue(우선순위 큐) 사용)

• 모든 비교에서 1번째, 2번째로 크기가 작은 카드 묶음을 합치기 위해서 Priority Queue(우선순위 큐) 를 사용한다.
• 우선순위 큐에 모든 카드 묶음을 넣고 1번째, 2번째로 크기가 작은 카드 묶음을 꺼내서 카드를 합친다.
• 또한 이렇게 합쳐진 카드 묶음을 다시 우선순위 큐에 넣어서 다른 카드 묶음과 크기를 비교한다.

import java.io.*;
import java.util.PriorityQueue;

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());    //총 카드 묶음 개수
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            pq.offer(Integer.parseInt(br.readLine()));
        }

        int result = 0;
        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            int sum = a + b;

            result += sum;
            pq.offer(sum);	//합친 카드묶음을 큐에 넣는다.
        }
        
        System.out.println(result);
    }
}

 

---

 

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈