[파이썬, 자바] 백준 - 1715 (그리디 알고리즘, 우선순위 큐)

https://www.acmicpc.net/problem/1715

 

처음 이 문제를 봤을 때는 시간복잡도 내에 어떻게 풀지 전혀 감을 잡지 못 했지만,

 

우선순위 큐를 알고 있는 지금은 쉽게 풀 수 있었던 문제다.

 

<우선순위 큐(Priority Queue)>

먼저 들어온 데이터가 먼저 나가는 FIFO 형태의 일반적인 큐와 달리,

 

들어온 순서에 상관없이 우선순위가 높은 데이터가 먼저 나가는 큐이다.

 

 

<왜 우선순위 큐를 써야 하나?>

문제 예제를 보면, 10, 20, 40의 카드 뭉치가 있을 때, 가장 적게 비교하여 합치는 방법은 (10 + 20) + (30 + 40) = 100이다.

 

즉, 적은 수의 카드 뭉치들부터 뭉치면 최소 횟수로 비교하여 합칠 수 있는 것이다.

 

이 예제만으로는 감이 안 잡혔다.

 

"그냥 큐에 크기 순으로 넣고 두 개씩 뽑으면서 더하고, 더해서 나온 새로운 숫자를 다시 큐에 넣는 식으로 진행하면 되겠는데?"

 

다른 예를 보자.

5
10
30
60
70
80

이렇게 문제가 주어졌을 때,

 

<초기 Queue>

Queue [10, 30, 60, 70, 80]

 

처음 비교는 10과 30이다. 그렇게 40번의 비교를 한다. 그리고 다시 큐에 삽입. (현재 Queue [60, 70, 80, 40])

 

다음 비교는? 40과 60이다. 그러나 현재 큐에서 뽑히는 두 개의 수는 60과 70이다. 이런 경우 때문에 우선순위 큐를 사용해야 하는 것이다.

 

우선순위 큐라면 처음 연산에서 40을 삽입하고 두 개의 수를 뽑을 때, 자동으로 제일 작은 40과 60을 내보낸다.

 

 

파이썬에서는 우선순위 큐를 PriorityQueue와 heapq로 구현할 수 있다.

 

자바에서는 우선순위 큐를 PriorityQueue로 구현할 수 있다.

 

Code(Python)

import heapq
import sys
input = sys.stdin.readline

N = int(input())
cards = [] # heapq의 경우 우선순위큐 객체를 따로 선언하는 것이 아니라, 기본 리스트 객체를 사용한다.
for _ in range(N):
    heapq.heappush(cards, int(input())) # 우선순위 큐에 데이터 삽입(기본 리스트를 사용하기 때문에 리스트 객체도 파라미터로 넣어준다.)
result = 0
while len(cards) > 1: # 우선순위 큐에 데이터가 한 개면 더 이상 비교를 진행할 수 없기 때문에 반복문 탈출
    sub = heapq.heappop(cards) + heapq.heappop(cards) # 큐에서 데이터 추출(단순히 리스트 객체만 파라미터로 넘기면 된다.)
    result += sub # 두 카드 뭉치를 비교한 횟수를 결과값에 저장하고,
    heapq.heappush(cards, sub) # 다시 우선순위 큐에 삽입
    
print(result)

 

Code(Java)

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

public class Boj_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> queue = new PriorityQueue<>(); // 우선순위 큐 객체 생성
        for (int i = 0; i < N; i++) {
            queue.add(Integer.parseInt(br.readLine())); // 우선순위 큐에 데이터 삽입
        }

        int result = 0;
        while (queue.size() > 1) {
            Integer num1 = queue.poll(); // 우선순위 큐에서 데이터 추출
            Integer num2 = queue.poll();

            result += num1 + num2;
            queue.add(num1 + num2);
        }

        System.out.println(result);
    }
}