문제

BOJ 1715, 카드 정렬하기

핵심

• 입력의 크기가 $10^5$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 매우 많은 숫자 묶음이 주어지고, 매번 두 묶음씩 골라 합친다. 카드 개수만큼 비교하여 최소한의 비교 횟수를 구해야 한다.
• 해당 문제를 직관적으로 접근한 그리디 알고리즘을 적용했다. 매번 가장 작은 두 묶음을 합치면 비교 횟수가 최소가 된다. 만약 가장 작은 두 묶음을 합치지 않았을 때도 비교 횟수가 최소로 될 수 있는가? 그렇지 않다고 생각하여 처음 명제를 참으로 보고 해결했다.

개선

코드

시간복잡도

• $O(N\times log_2N)$

C++

#include <iostream>
#include <queue>
using namespace std;

int n;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	auto comp = [](auto& a, auto& b) { return a > b; };
	priority_queue<int, vector<int>, decltype(comp)> pq(comp);
	cin >> n;
	while (n--) {
		int num;
		cin >> num;
		pq.push(num);
	}	
	int cnt = 0;
	while (pq.size() > 1) {
		int a = pq.top();
		pq.pop();
		int b = pq.top();
		pq.pop();
		cnt += (a + b);
		pq.push(a + b);
	}
	cout << cnt;
}

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            pq.add(num);
        }
        int ans = 0;
        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            ans += a + b;
            pq.add(a + b);
        }
        System.out.println(ans);
    }
}