algospot :: STRJOIN 문자열 합치기

문제 : 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);