[백준 / BOJ] C++ 1545 안티 팰린드롬

1545번: 안티 팰린드롬

 

문제

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

1545번: 안티 팰린드롬

 

 

풀이

어떤 문자열 P에 대해 P[i]와 P[n-i-1] (0 ≤ i<(n-1)/2, n = P의 길이)이 모두 다를 때, P는 안티 팰린드롬 문자열이다. 이 문자열을 재배치해서 안티 팰린드롬 문자열을 만드는 문제다. 단, 사전순으로 가장 앞서는 경우를 만들어야 한다.

 

string s를 사전순으로 앞서는 순서로 만들기 위해 먼저 정렬을 해준다. 그리고 가운데부터 좌, 우로 차례대로 나아가며 두 문자가 같은지 비교하기 위해 투 포인터(left, right)를 사용했다.

 

만약 두 문자가 같다면 사전 순으로 앞서기 위해 뒤, 즉 s[right]를 s[right]보다 뒤에 있는 문자와 swap 할 것이다. 그러나 만약 s[right] == s[right+1]라면 swap 하더라도 의미가 없으므로 index를 1씩 계속 더해준다. 다른 문자가 나온 순간 s[right]와 s[index]를 swap해주고 left--, right++ 해준다. 이를 left나 right가 범위 끝까지 가도록 반복한다. 

 

그러나 만약 swap하기 위한 문자를 찾다가 결국 index가 범위를 초과하면 바꿀 수 있는 문자가 없다는 뜻이므로 -1을 출력하고 프로그램을 종료해 줬다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string s;
  cin >> s;
  int size = s.size();
  sort(s.begin(), s.end());
  int left, right;
  if (size % 2 == 0) {
    left = size / 2 - 1;
    right = size / 2;
  } else {
    left = size / 2 - 1;
    right = size / 2 + 1;
  }
  while (left >= 0) {
    if (s[left] == s[right]) {
      int idx = right;
      while (s[idx] == s[right]) {
        idx++;
        if (idx == size) {
          cout << "-1\n";
          return 0;
        }
      }
      char tmp = s[right];
      s[right] = s[idx];
      s[idx] = tmp;
    }
    left--;
    right++;
  }
  cout << s << '\n';
  return 0;
}