2385번: Secret Sharing

https://www.acmicpc.net/problem/2385


$O(n^2)$



먼저, 0으로 시작하면 안된다는 조건을 무시하고 생각해보자.

나열할 때, 대충 생각할 수 있는 방법으로는 사전순 정렬이 있다. 물론 이 방법에는 다음과 같은 반례가 존재한다.

345

34512

사전순 정렬 후 나열: 34534512

정해: 34512345


기본적으로 사전배열이 최적해를 도출해내는 것은 맞다.
모든 조각들 p, q 쌍에 대해 사전순 비교를 할 때 문자열의 끝에 도달하기 전에 순서가 결정된다면 (p,q)사전순 비교를 통해 답을 내놓아도 상관없다.
위의 예와 같이 공백문자열에 의해 순서가 뒤바뀌는 것이 문제이다.

공백문자열에 의해 순서가 뒤바뀔 수 있는 쌍들은 (p,q)사전식 비교를 통해 정렬했을 때 인접하게 된다는 것을 알 수 있다.
고로 서로 간의 우선순위만 따지면 되며(즉, p와 q사이에 어떤 문자열도 오지 않을 것이다.) 이것을 해결하기 위해 string p와 q를 비교할 때 p+q 와 q+p를 사전순 비교하면 된다.



0이 처음에 올 수 없다는 조건을 추가해도 위에서 쓰인 아이디어를 적용하면 어렵지 않게 해결된다.

0이 첫글자인 string을 위 비교함수로 정렬하여 나열한 문자열을 t라고 하자.

암호 키의 첫 번째에 오는 조각은 p+t+q와 q+t+p를 비교하여 사전순으로 가장 앞에 오는 p이다.

p 뒤에 나머지 문자열들을 정렬한대로 나열하면 된다.
아무거나 하나씩 제일 앞에 두고 나머지 조각들을 위와 같이 정렬해서 따져봐도 된다. 이 경우 시간복잡도는 $O(n^2lgn)$

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s[100], t;
bool cmp1(string i, string j) { return i + j<j + i; }
bool cmp2(string i, string j) { return i + t + j<j + t + i; }
int n, i;
int main() {
    cin >> n;
    for (i = 0; i<n; i++) cin >> s[i];
    sort(s, s + n, cmp1);
    for (i = 0; i<n && s[i][0] == '0'; i++) t += s[i];
    if (i == n) cout << "INVALID";
    else {
        int p = min_element(s + i, s + n, cmp2) - s;
        cout << s[p];
        for (int i = 0; i<n; i++) if (i^p) cout << s[i];
    }
    return 0;
}