[1715] 카드 정렬하기

✔ 카드 정렬하기

[백준 1715]

문제 분석하기

먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미치게 되므로

카드 묶음의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법

그러므로 현재 데이터 중 가장 작은 카드의 개수를 가진 묶음 2개를 뽑아 합친 후

새로운 카드 묶음을 다시 데이터에 넣고 정렬하는 것을 반복해야 하므로 우선순위 큐를 이용

손으로 풀어보기

1. 현재 카드의 개수가 가장 작은 묶음 2개를 선택해 합침
2. 합친 카드 묶음을 다시 전체 카드 묶음 속에 넣음
3. 카드 묶음이 1개만 남을 때까지 반복함

슈도코드 작성하기

N(카드 묶음 개수)
pq(우선순위 큐)
for(N만큼 반복하기) {
    우선순위 큐에 데이터 저장하기
}
while(우선순위 큐 크기가 1이 될 때까지) {
    2개 카드 묶음을 큐에서 뽑음(remove 연산)
    2개 카드 묶음을 합치는 데 필요한 비교 횟수를 결괏값에 더함
    2개 카드 묶음의 합을 우선순위 큐에 다시 넣음(add 연산)
}
누적된 비교 횟수 출력하기

코드 구현하기

/**
 * 1715) 카드_정렬하기
 */
public class D033_1715 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(카드 묶음 개수)
        int N = sc.nextInt();
        // pq(우선순위 큐)
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        // 우선순위 큐에 데이터 저장하기
        for (int i = 0; i < N; i++) {
            int data = sc.nextInt();
            pq.add(data);
        }
        int data1 = 0;
        int data2 = 0;
        int sum = 0;
        while (pq.size() != 1) {
            // 2개 카드 묶음을 큐에서 뽑음
            data1 = pq.remove();
            data2 = pq.remove();
            // 2개 카드 묶음을 합치는 데 필요한 비교 횟수를 결괏값에 더함
            sum += data1 + data2;
            // 2개 카드 묶음의 합을 우선순위 큐에 다시 넣음
            pq.add(data1 + data2);
        }
        // 누적된 비교 횟수 출력하기
        System.out.println(sum);
    }
}