알고리즘

algospot :: STRJOIN 문자열 합치기

happilee12 2017. 10. 17. 22:17
반응형

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

알고리즘 문제 해결 전략 p. 382

책을 참고하지 않고 코드를 작성함



[알고리즘 STEP. 1]

문제의 예제에서 보여주듯,  짧은 문자열 부터 합쳐나가면서 완성해야 가장 효율적이다. 

책에서는 이렇게 설명한다


각 비용을 분해해 보면, 한 문자열을 만드는 데 발생하는 총 비용은 이 문자열이 병합되는 횟수에 문자열의 길이를 곱한 것이라는 것을 알 수 있습니다.

따라서 문자열의 길이가 길수록 트리의 윗쪽에 가깝고, 짧을수록 아래에 가까워야 한다는 직관을 얻을 수 있습니다.

- 알고리즘 문제 해결 전략 p. 383


이를 구현하는 알고리즘은 다음과 같다. 

문제에서 주어지는 문자열 길이 배열을 크기가 작은 순으로 Sort한 배열을 A라고 할 때

1. A에서 가장 작은 값 두개를 더한 후(=sum) 지우고, 

2. return (A에서 가장 작은 숫자 두개를 합친 값) 

3. A에 sum 을 삽입

4. A를 다시 Sort 한 후 재귀적으로 시행



문제에서 주어진 3개의 예제에 대해서는 다음과 같이 진행된다.

빨간색으로 표시한 숫자는 전의 배열에서 가장 작은 두 숫자를 합쳐서 삽입된 값이다.




이를 바탕으로 greedy 코드를 작성하면 다음과 같이 된다.


 int greedy(vector<int> &strLength){

    if(strLength.size()<=1) return 0;
    int sum = pop_front(strLength)+pop_front(strLength); // 가장 작은 값 + 두번째로 작은 값 & 배열에서 두 값 삭제
    strLength.push_back(sum); // 두 값의 합을 배열에 넣고
    sort(strLength.begin(), strLength.end()); // 배열 재정렬
    return sum + greedy(strLength);
}




[최종코드]

 

#include <iostream>
#include <algorithm>
#include <vector>

#define FOR(var, ed) for(int var = 0; var<ed; var++)
using namespace std;

//input
int tc, n;
void printVect(const vector<int> &a){
    for(int x : a)
        cout << x << " ";
    cout << endl;
}
int pop_front(vector<int> &a){
    int ret = a.front();
    a.erase(a.begin());
    return ret;
}

int greedy(vector<int> &strLength){
    if(strLength.size()<=1) return 0;
    int sum = pop_front(strLength)+pop_front(strLength); // 가장 작은 값 + 두번째로 작은 값 & 배열에서 두 값 삭제
    strLength.push_back(sum); // 두 값의 합을 배열에 넣고
    sort(strLength.begin(), strLength.end()); // 배열 재정렬
    return sum + greedy(strLength);
}
int main(){
//    freopen("input.txt", "r", stdin);
    cin >> tc;
    while(tc--){
        cin >> n;
        vector<int> strLength(n);
        FOR(i, n)
            cin >> strLength[i];
        sort(strLength.begin(), strLength.end());
        cout << greedy(strLength) << endl;

    }
}



[새로 알게 된 것들]

- 벡터에서 pop_front 

int pop_front(vector<int> &a){
int ret = a.front();
a.erase(a.begin());
return ret;
}

- 벡터에서 sort

sort(strLength.begin(), strLength.end());

- 벡터에서 i번째 인덱스에 삽입

a.insert(a.begin()+i, value);

반응형