백준 1522 - 문자열 교환

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

힌트

특정한 상태를 만들어 보는 방법을 생각해보자.

 

그리고 원형의 상태가 문제 풀이에 어떤 영향을 미치는지도 생각해보자.

풀이

우리는 aaaabbbb 꼴과 같은 상태를 만들어 볼 것이다.

 

그러면 왼편의 b는 오른편의 a와 바꿔야 할 것이다.

 

물론 원형이라는 조건 하에 abbbbaaa 같은 문자열도 성립됨을 상기하자.

 

다만 abbbbaaa를 만드는 것과 aaaabbbb는 구현상 모순이다.

 

우리는 이 모순을 극복하기 위해 원형이라는 점을 이용해 문자열을 쉬프트 할 것이다.

 

그러면 문제는 다음과 같이 바뀐다.

 

"원본 문자열을 x번 쉬프트 한 상태에서 aaaabbbb... 꼴로 만드는 연산 횟수"

 

그러면 각 상태에서 투 포인터로 스왑 횟수를 세고 그의 최솟값을 구하면 그게 정답이 된다.

 

원형으로 이어진 수열은 일직선 수열에 2배 한 것과 같으므로 주어진 문자열을 두 배로 복제하고 각 구간마다 투 포인터를 시행하는 방법으로 구현할 수 있다.

 

자세한 코드는 밑을 참조한다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int ans = 1e9;
string s;
 
void solve()
{
  cin >> s;
  int sz = s.size();
  for (int i = 0; i < sz; i++) s.push_back(s[i]);
  int stt = 0, end = sz - 1;
  while (end < s.size())
  {
    int tmp = 0;
    int l = stt, r = end;
    while (l < r)
    {
      if (s[l] == 'a')
      {
        ++l;
        continue;
      }
 
      if (s[r] == 'b')
      {
        --r;
        continue;
      }
 
      ++tmp;
      ++l, --r;
    }
 
    ans = min(tmp, ans);
    ++stt, ++end;
  }
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록