백준 1464번 - 뒤집기 3 [C++]

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

 

 

풀이

 

문자열의 $i$번째 문자를 처리할 때, 결과적으로 그 문자를 지금까지 만든 문자열의 맨 앞에 붙이거나 / 맨 뒤에 붙이는 두 선택으로 생각할 수 있다.

 

증명

 

입력 문자열 $S = s_1s_2...s_N$

 

$i$번째 결정을 하는 순간, 문자열은 (결정된 $i - 1$개의 문자로 이루어진 문자열) + $s_i$ + (나머지) 가 된다.

여기서 "결정된 $i - 1$개의 문자로 이루어진 문자열"을 $P$ 라 해보자. 다시 써보면, $P$ + $s_i$ + (나머지)이다.

그리고 문자열 $P$ 만 보면 만들 수 있는 사전순으로 가장 빠른 문자열이다.

 

$i$ 단계에서 할 수 있는 선택

1. 안 뒤집는다.
   $P$ + $s_i$ + (나머지)
2. 뒤집는다.
   $reverse(P + s_i)$ + (나머지) $ = s_i + reverse(P) $ + (나머지)

뒤집는 경우, $P$ 가 뒤집히기 때문에 주의가 필요하다. 뒤집히는 경우에도 사전순으로 빠른 문자열을 유지할 수 있어야한다.

따라서 $i$번째 단계에서 뒤집는다면, $i - 1$ 번째 단계에서도 똑같이 뒤집기를 수행해야한다.

\[
P+c
\;\xrightarrow{\text{flip }(i-1)}\;
\operatorname{rev}(P)+c
\;\xrightarrow{\text{flip }i}\;
\operatorname{rev}\big(\operatorname{rev}(P)+c\big)
=
c+P
\]

 

결국 $i$단계의 입맛에 맞추어 $i - 1$단계의 뒤집기 여부를 판단할 수 있다.

 

정답 코드

[C++17]

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;

void solve() {
  string s; cin >> s;
  string ans = "";
  for (auto x : s) {
    if (x + ans <= ans + x) ans = x + ans;
    else ans = ans + x;
  }
  cout << ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}