그리디 알고리즘 예제 - 2

문제(백준(1715번 - 카드 정렬하기))

문제 분석

• 잘 생각해보면 먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미치는 것을 알 수 있다.

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

• 현재 데이터 중 가장 작은 카드의 개수를 가진 묶음 2개를 뽑아야 하고, 이 2개를 기준으로 합친 새로운 카드 묶음을 다시 데이터에 넣고 정렬해야 한다.

• 즉, 데이터의 삽입, 삭제, 정렬이 자주 일어나므로 우선순위 큐를 이용해야 한다.

손으로 풀어보기

1. 현재 카드의 개수가 가장 작은 묶음 2개를 선택해 합친다.

2. 합친 카드 묶음을 다시 전체 카드 묶음 속에 넣는다.

3. 과정 1~2를 카드 묶음이 1개만 남을 떄까지 반복한다.

슈도코드

n(카드 묶음 개수)
pq(우선순위 큐)

for n 반복:
    pq에 데이터 저장
    

while 우선순위 큐 크기가 1이 될 때까지:
    2개 카드 묶음을 큐에서 뽑음
    2개 카드 묶음을 합을 결과에 더함
    2개 카드 묶음의 합을 우선순위 큐에 다시 넣음
    
누적된 결과 출력

코드 구현 - 파이썬

from queue import PriorityQueue

n = int(input())
pq = PriorityQueue()

for _ in range(n):
    pq.put(int(input()))

total = 0
while pq.qsize() > 1:
    data1 = pq.get()
    data2 = pq.get()
    sum = data1 + data2
    total += sum
    pq.put(sum)

print(total)

코드 구현 - 자바

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

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());

        Queue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }

        int total = 0;
        while (pq.size() > 1) {
            int data1 = pq.poll();
            int data2 = pq.poll();
            int hap = data1 + data2;

            total += hap;
            pq.add(hap);
        }
        System.out.println(total);
    }
}