문자열 장식( BOJ 1294 )

문제 : https://www.acmicpc.net/problem/1294

1294번: 문자열 장식

 

문제 파악하기

N개의 문자를 적절하게 분해해서 사전순으로 가장 앞에 있는 하나의 문자를 만드는 문제입니다. 모든 문자의 순서를 맞춰야 하기 때문에 앞에서부터 하나씩 가져와야합니다. 문제를 처음 보면 사전순으로 가장 빠른 문자를 마냥 선택하면 될듯 하지만 aaa / aab 와 같이 동일한 문자가 반복될 때, 어떤 문자에서 a를 가져오는지에 따라 결괏값이 달라지기에 좀 더 세밀한 조건이 필요합니다.

 

문제 해결하기

단순히 앞 자리의 가장 빠른 문자를 선택하기에는 허술한 부분이 많습니다. 그렇기에 선택에 있어 적절한 조건이 필요하며, 여기서는 두 문자열을 더해서 비교하는 방식을 선택할 수 있습니다. 예를 들어, aaa 와 aab가 있다고 가정해보겠습니다. 이 경우, 두 문자를 더해서 나올 수 있는 경우의 수는 총 2가지로, aaaaab와 aabaaa가 있습니다. 두 결과 중 좀 더 사전순으로 앞서는 결과는 aaaaab가 되며, 우리는 aaa와 aab 중 aaa를 먼저 선택해서 넣는 것이 좀 더 최적값에 가깝다는 걸 확인할 수 있습니다. 이처럼 모든 문자를 비교할 때에 두 문자열을 더해서 비교할 수 있으며, 이런 그리디 방식을 exchange argument 이라고 합니다.

 

문자열을 비교하는 방식을 알아냈으니 이제는 문자열을 선택하는 방식을 떠올려봅시다. 단순히 N개의 모든 값을 저장한 다음에 값을 없앨 때마다 정렬하는 방식을 사용해도 되지만, 우선순위 큐를 사용하면 좀 더 깔끔하게 처리할 수 있습니다. 또한, 모든 값이 아닌 각각의 값을 인접한 문자열끼리 결합하여 하나의 문자로 만드는 분할정복 방식을 사용하면 효율적인 처리 또한 가능합니다. 이렇게 여러 방식을 사용해서 문자열에서 문자를 하나씩 추출하여 하나의 문자로 만들면 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
string s;
vector< string > inp;
 
struct cmp {
    bool operator()(string a, string b) {
        return a+b > b+a;
    }
};
priority_queue< string, vector< string >, cmp > q;
 
 
string merge(int l, int r) {
    if(l == r) return inp[l];
    
    string lt, rt, ret="";
    
    q.push(merge(l, (l+r)/2));
    q.push(merge((l+r)/2+1, r));
    
    while(!q.empty()) {
        string t = q.top();
        q.pop();
        
        ret = ret + t[0];
        if(t.size()>1) q.push(t.substr(1, t.length()-1));
    }
    
    return ret;
}
 
int main() {
    cin >> N;
    for(int i=0;i<N;i++) {
        cin >> s;
        inp.emplace_back(s);
    }
    
    cout << merge(0, N-1);
    
}
/*
4
DD
DDA
DDAF
DDFGA
ans:DDADDADDDDFFGA
 
2
DDDA
DDDADDDB
ans: DDDADDDADDDB
*/
 

후기

쉬운 듯, 어려웠던 문제입니다. 평범하게 모든 문자열을 탐색해서 정렬하기에는 너무도 오래 걸리기에 효과적인 방식이 필요했습니다. 이전에 풀어봤던 문제인 큰 수 만들기 때 삽질했던 경험이 없었다면 오랜 시간이 걸렸을 듯 합니다. 그리디 기법을 연습하기에 적절하며, 문제를 푼 이후에는 [ Exchange argument ]라는 주제로 공부할 수 있어 유익했던 문제입니다.

 

참고

Exchange argument : http://www.secmem.org/blog/2019/11/16/Exchange-argument/