[백준 C++] 1213번 : 펠린드롬 만들기

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

 

풀이 :

- 주어진 문자열을 펠린드롬으로 즉, 앞에서 읽었을 때와 뒤에서 읽었을 때 똑같은 문자열로 만들어야 한다.

- 펠린드롬으로 만들 수 없다면 I'm Sorry Hansoo를 출력한다.

- 펠린드롬으로 만들 수 없는 경우는 주어진 문자열의 알파벳 갯수 중 홀수인 알파벳이 2개 이상인 경우이다.

- 따라서 홀수인 알파벳이 몇 개인지가 제일 중요하다.

- 2개 이상이라면 만들 수 없고, 1개라면 중간에 홀수인 알파벳을 출력한다.

- 사전순이라고 했기 때문에 알파벳을 카운트한 배열을 오름차순으로 탐색하며 출력하고, 

   다시 내림차순으로 탐색하며 출력하면 자연스럽게 정렬된 상태로 펠린드롬을 만들 수 있다.

 

코드 :

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int alphabet[30] = {0, }, cnt = 0;
    string s;
    char flag, ans;

    cin >> s;
    for(int i=0; i<s.size(); i++){
        alphabet[s[i]-'A']++; //int배열이기 때문에 'A'를 빼고 알파벳 갯수를 세어준다
    }
    for(int i=0; i<27; i++){
        if(alphabet[i]%2 == 1){ 
            cnt++; //홀수인 알파벳이 몇 개인지 세어준다
            flag = i+'A'; //cnt가 1일 경우 중간에 한번 출력해줘야 하기 때문에 flag에 저장해둔다
        }
    }
    if(cnt > 1){ //cnt가 1보다 크다면 펠린드롬을 만들 수 없다
        cout << "I'm Sorry Hansoo";
    }else{
        for(int i=0; i<27; i++){ //0부터 올라가며 탐색을 한다
            if(alphabet[i] > 0){ 
                for(int j=0; j<alphabet[i]/2; j++){ //펠린드롬으로 만들기 위해 갯수의 절반까지만 출력한다
                    ans = i+'A'; //바로 출력하면 아스키코드로 나와서 char 변수에 넣고 출력해줬다
                    cout << ans;
                }
            }
        } 
        if(cnt == 1){ //for문이 끝났다는건 절반을 출력했다는 것
            cout << flag; //홀수가 하나 있을 경우 해당 알파벳을 출력한다
        }
        for(int i=27; i>=0; i--){ //위에서부터 내려오며 탐색한다
            if(alphabet[i] > 0){
               for(int j=0; j<alphabet[i]/2; j++){
                    ans = i+'A';
                    cout << ans;
                }  
            }
        }
    }
    cout << '\n';
}