[구현 / BOJ 1213 / C++] 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

1) A부터 Z까지 각 문자의 개수를 확인하여 배열에 저장해준다.
2) 문자의 개수가 홀수라면, 그 문자를 가운데(mid) 문자로 지정하고 문자의 개수를 하나 빼주어 짝수 취급한다.
2-1) 문자의 개수가 홀수 인것이 두개이상 나오면(flag>=2) 불가능하다고 출력한다. 
3) 문자의 개수가 짝수라면, 할 수 있는 만큼 ret 문자열에 앞뒤로 한개씩 붙여준다.
4) mid가 존재한다면 ret 가운데에 mid를 삽입하고 출력한다.

이 문제에서 주어진 알파뱃이 palindrome을 이루러면 어떤 조건이어야되는지 알아야한다.

 

palinrome이 가능한 단어들을 생각해보면 답이 금방 나올 수 있다.

 

1) AABB 가능

2) ABA 가능

3) ABBBA 가능

4) AAABBB 불가능 

 

짝수개씩 있는 문자의 개수와 상관없이

홀수개씩 있는 문자가 여러개일 경우는 palindrome을 절대 만들 수 없다.

즉, 홀수개씩 있는 문자는 반드시 한 개 이하여야만 가능하다.

 

cnt[i]&1 은 홀수일 경우 참이라는 뜻이다.

 

cnt['A']++; 같은 표현을 눈여겨 보면 좋을 것 같다.

 

#include <bits/stdc++.h>

using namespace std;

string s, ret;
int cnt[200];
int flag;
char mid;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> s;
    for(char i : s) cnt[i]++;
    for(int i = 'Z' ; i >= 'A' ; i--){
        if(cnt[i]){
            if(cnt[i]&1){
                mid = char(i);
                flag++;
                cnt[i]--;
            }
            
            if(flag==2) break;
            
            for(int j = 0 ; j < cnt[i] ; j+=2){
                ret += char(i);
                ret = char(i) + ret;
            
            }
        }
    }
    
    
    if(mid) ret.insert(ret.begin() + ret.size()/2, mid);
    if(flag==2) cout << "I'm Sorry Hansoo";
    else cout << ret;
    
    
    
}