BOJ 2385 - Secret Sharing

BOJ 2385 - Secret Sharing

사실상 이문제는 이제 백준의 웰노운이라고 봐도 무방하다.

그 누군가는 증명했을 명제인 두 문자열 $a,b$ 가 있을 때 $ab$가 $ba$ 보다 사전순으로 앞선다면 전체 순서에서도 $a$가 $b$ 앞에 있어야 한다라는 것이 참이기 때문이다.

leading zero인 경우를 고려해주며 적절히 구현해주면 된다.

void solve() {  
   int n;  
   cin >> n;  
   vs a(n);  
   fv(a);  
  
   bool can = 0;  
   for (int i = 0; i < n; i++) {  
      if (a[i][0] != '0') can = 1;  
   }  
   if (!can) {  
      cout << "INVALID";  
      return;  
   }  
   vs ans;  
   for (int i = 0; i < n; i++) {  
      if (a[i][0] == '0') continue;  
      vs b;  
      for (int j = 0; j < n; j++) if (i != j) b.pb(a[j]);  
      sort(all(b), [&](auto &a, auto &b) -> bool {  
         return a + b < b + a;  
      });  
      string c = a[i];  
      for (string &x: b) c += x;  
      ans.pb(c);  
   }  
   sort(all(ans));  
   cout << ans[0];  
}