백준 1545 - 안티 팰린드롬

문제링크: https://www.acmicpc.net/problem/1545

P[i] 와 P[n-i-1] 이 다르기만하면된다.

이때 하나 발견할 수 있는 것이
특정 문자의 수가 길이의 절반을 넘겨버리면 답이 나올 수 없는 상황이 된다.

주어진 문자열의 문자들을 임의로 배치가 가능하므로
문자열 P를 사전순으로 재정렬해준다.

이때 특정문자의 수가 절반을 넘기지 않으면
사전순으로 정렬된 것의 앞쪽부터 절반사이즈만큼 그대로 가져가는게 이득이다.
(절반을 기준으로 양쪽 각각의 idx가 서로 매칭되기때문에
앞에두던 뒤에두던 안티 펠린드롬을 판별하는데 영향을 주지 않는다)

다음으로 절반 이후의 상황만 파악하면 되는데

절반 이후의 문자들도 사전순으로 정렬되어있으므로
P[i] 와 P[n-i-1] 이 다르면
n-i-1 을 기준으로 뒤의 것의 문자와
교환을 고려해보는게 최선임을 알 수 있다...

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
string n;
int main(){
    cin>>n;
    int len = n.size();
    sort(n.begin(),n.end());
    vector<int> cnt(26);
    for(int i=0;i<len;i++){
        char now = n[i];
        cnt[now-'a'] = upper_bound(n.begin(),n.end(),now)-lower_bound(n.begin(),n.end(),now);
        if(cnt[now-'a']>(len+1)/2){
            cout<<"-1"<<"\n";
            return 0;
        }
        i+=cnt[now-'a']-1;
    }
    for(int i=(len+1)/2;i<len;i++){
        if(n[i]==n[len-i-1]){
            for(int t=i;t<len;t++){
                if(n[t]!=n[i]){
                    swap(n[t],n[i]);
                    break;
                }
            }
        }
    }
    cout<<n<<"\n";
}