백준 13975 파일 합치기 3(c++)

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

13975번: 파일 합치기 3

<코드>

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

int main()
{
	priority_queue<long long,vector<long long>,greater<long long>>pq;
	int t;
	cin>>t;
	int n;
	while(t--)
	{
		long long sum =0;
		cin>>n;
		for(int i=0;i<n;i++)
		{
			int a;
			cin>>a;
			pq.push(a);
		}
		while(pq.size()>1)
		{
			long long n1 = pq.top();
			pq.pop();
			long long n2 = pq.top();
			pq.pop();
			sum += (n1+n2);
			pq.push(n1+n2);	
		}
		cout<<sum<<'\n';
		pq.pop();
	}
}

<풀이과정>

이 문제는 허프만 압축을 통해 풀어야 한다.

파일을 최소의 크기로 합치기 위해 최소 힙 기반 우선순위 큐를 하나 만들어준다.

그리고 빈도수가 낮은 두 개의 노드를 합쳐 새로운 노드에 합쳐주는 과정이 허프만 압축 알고리즘이다(그리디 알고리즘)

그러면 마지막에 하나의 노드가 남게되는데, 이는 pop해주고 새로운 테스트 케이스로 넘어가게 된다.

허프만 압축 알고리즘

<코드>

각 문자당 노드를 만들고, 그 문자의 노드의 빈도수를 노드에 저장
n개의 노드의 빈도수에 대해 우선순위 큐를 만들어준다(최소 힙 기반이므로, 가장 작은 수(빈도수가 낮은 것)부터 큐에 들어가게 된다.
while(Q의 노드수>1)
{
	가장 작은 수를 pop한다.
    pop한 두 개의 수 a,b를 다른 노드에 삽입
    num = a + b; // 두 개의 수를 합한다.
    그 이후에 다시 Q에 삽입
}