ALGOSPOT STRJOIN 알고스팟 문자열 합치기

ALGOSPOT STRJOIN 알고스팟 문자열 합치기

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
#include <algorithm>
#include<set>
using namespace std;
 
//문자열들의 길이가 주어질 때 하나로 합치는 최소 비용을 반환한다.
int concat(const vector<int> &lengths) {
    //최소 큐를 선언한다.
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int i = 0; i < lengths.size(); i++) {
        pq.push(lengths[i]);
    }
    int ret = 0;
    //원소가 하나 이상 남은 동안 반복한다.
    while (pq.size() > 1) {
        //가장 짧은 문자열 두개를 찾아서 합치고 큐에 넣는다.
        int min1 = pq.top(); pq.pop();
        int min2 = pq.top(); pq.pop();
        pq.push(min1 + min2);
        ret +=(min1 + min2);
    }
    return ret;
}
 
 
int main(void) {
    int cases;
    cin >> cases;
    while (cases--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (int i = 0; i < n; i++)
            cin >> arr[i];
 
        cout << concat(arr) << endl;
    }
    return 0;
}

문제 출처:https://algospot.com/judge/problem/read/STRJOIN

출현 확률이 문자열 길이로 바뀌었을 뿐 사실 허프만 코드알고리즘을 각색한 문제입니다.