algospot STRJOIN

문제 링크입니다: https://algospot.com/judge/problem/read/STRJOIN

허프만 코드와 비슷한 개념으로 문제를 풀면 됩니다.

(https://ko.wikipedia.org/wiki/%ED%97%88%ED%94%84%EB%A7%8C_%EB%B6%80%ED%98%B8%ED%99%94)

허프만 코드는 출현빈도가 높은 문자를 트리 상단에 배치하는데 이 문제에서는 출현빈도 대신 문자열의 길이가 길수록 트리 상단에 배치하면 됩니다.

예를 들어 두 번째 테스트 케이스를 그림으로 표현해봤습니다.

원 안에 있는 숫자들이 초기에 입력된 문자열의 길이이고, 네모가 합쳤을 때 드는 비용입니다.

즉, 네모를 모두 합치면(2+5+7+12) 문자열을 합치는데 드는 최소 비용(26)이 나옵니다.

/*

n개의 문자열을 순서와 상관없이 합쳐서 한 개의 문자열로 만들고 싶다.

그러나 문자열을 합치는 순서에 따라 전체 비용이 달라지는데

합칠 때 최저비용을 찾으시오

*/

#include <iostream>

#include <queue>

#include <vector>

#include <functional>

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 result = 0;

        //원소가 하나 이상 남은 동안 반복

        while (pq.size() > 1)

        {

               //가장 짧은 문자열 두 개를 찾아서 합치고 큐에 넣는다

               int min1 = pq.top();

               pq.pop();

               int min2 = pq.top();

               pq.pop();

               pq.push(min1 + min2);

               result += min1 + min2;

        }

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               int strNum;

               cin >> strNum;

               if (strNum < 1 || strNum>100)

                       exit(-1);

               vector<int> lengths;

               for (int i = 0; i < strNum; i++)

               {

                       int len;

                       cin >> len;

                       lengths.push_back(len);

               }

               cout << concat(lengths) << endl;

        }

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략