1213

 

문제 요약

 

 들어온 문자열을 분해하여 팰린드롬을 만들어야 한다. 

 

 

입력

 

알파벳 대분자의 최대 50글자.

 

 

출력

 

만든 팰린드롬 출력, 불가능할 때는 정해진 문자열 출력

 

정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력

 

 

 

풀이

 

각 문자의 숫자를 세서 저장한다. 홀수가 2개 이상이면 팰린드롬을 만들 수 없다.

 

이제 만드는 것이 문제인데.. 

 

다음과 같이 정의해 보자.

 

1. 이름을 입력받는다.

 

2. count 배열을 생성하여 들어온 문자열의 개수를 저장한다.

 

3. 오름차순으로 표현해야 하기 때문에 Z부터 반복한다.

 

4. 카운트가 존재하는 경우 

 

4.1 홀수인지를 판단한다.  홀수라면 해당 문자열을 변수에 저장하고 카운트 값을 감소시킨다.

 

4.2 만약 홀수가 두 개이상인 경우 반복을 중단하고 불가능 출력을 진행한다. 이를 위해 홀수 개수를 세는 변수를 선언한다.

 

4.3 짝수인 경우 출력 값 앞, 뒤에 붙인 이후 증감 연산자를 2개씩 설정하여 반복하도록 한다. 

 

5. 홀수가 1개인 경우 만들어진 출력 변수의 중앙에 값을 넣는다.

 

이를 코드로 표현하면 다음과 같다.

#include <bits/stdc++.h>

using namespace std;

string name, result;
int cnt[200], odd;
char mid;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //이름을 입력받는다.
    cin >> name;
    //count 배열을 생성하여 문자열 개수를 저장한다.
    for(char a: name) cnt[a]++;

    //Z부터 A까지 반복한다.
    for(int i = 'Z'; i >= 'A'; i--){
        //cnt 값이 존재한다면
        if(cnt[i]){
            //홀수를 판단한다. LSB와 1을 AND연산하여 값이 1인지 확인
            if(cnt[i] & 1){
                //홀수인 알파벳을 저장
                mid = char(i);
                //홀수 플래그를 1 증가
                odd++;
                // 카운트 개수 제거
                cnt[i]--;
            }

            //홀수가 2개 이상이면 break; 팰린드럼 불가능
            if(odd >= 2) break;

            //짝수이면 문자열에 앞 뒤로 추가하며 2개씩 진행
            for(int j=0; j < cnt[i]; j+=2){
                result = char(i) + result;
                result += char(i);
            }
        }
    }

    //홀수가 하나인 경우 출력 가운데 삽입
    if(mid) result.insert(result.begin() + result.size()/2, mid);

    //불가능 출력
    if(odd >= 2) cout << "I'm Sorry Hansoo\n";
    else cout << result << '\n';


    return 0;
}