[Algorithm #11] 1213 - 팰린드롬 만들기 (C++)

1. 문제 설명

1. A의 영어 이름을 받아서 팰린드롬을 만든다.
   -> 팰린드롬 : 앞 뒤가 똑같은 문자열 (기러기, 토마토, 우영우 ...)
2. 만든 팰린드롬 문자열을 출력, 만들지 못하면 I'm Sorry Hansoo를 출력

2. 문제 해결 전략

1. 우선 문자열(A의 영어 이름)을 입력받는다.
2. cnt배열을 이용하여 문자열에 각 문자들의 빈도수를 저장해둔다.
   -> why ? 팰린드롬수는 갯수가 홀수인 문자가 두 개 이상이면 만들 수가 없다
   EX) AACDBDD
3. iter문을 통해 홀수의 갯수를 세어본다(cnt에 저장).
4. 만약 cnt가 2보다 크거나 같고 0이 아니라면(홀수가 없는 경우 존재) I'm Sorry Hansoo를 출력하고 return문으로 main 함수를 바로 종료시킨다.
5. 아니라면 'Z'부터 'A'까지 반복문을 돌며 만약 홀수라면 mid에 해당 문자를 저장 시키고 count 배열에서 값을 감소시킨다.
6. 2중 반복문으로 카운팅 배열의 사이즈 만큼 돌며 앞 뒤로 글자를 하나씩 붙인다.
   EX) ACBAC -> CC -> ACAC
7. 만든 문자열 중간에 앞에서 구한 mid를 끼어 넣는다.
8. 만든 문자열을 출력

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

map<char, int> sen_cnt;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int cnt = 0;
    string s;
    string result;
    int mid = 0;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        sen_cnt[s[i]]++;
    }

    for (auto it: sen_cnt) {
        if ((it.second) % 2 == 1)
            cnt++;
    }

    if (cnt >= 2 && cnt != 0) {
        cout << "I'm Sorry Hansoo" << "\n";
        return 0;
    } else {
        for (int i = 'Z'; i >= 'A'; i--) {
            if (sen_cnt[i] % 2 == 1 && sen_cnt[i] != 0) {
                mid = char(i);
                sen_cnt[i]--;
            }
            for (int j = 0; j < sen_cnt[i]; j += 2) {
                result = char(i) + result;
                result += char(i);
            }
        }
    }
    if (mid)
        result.insert(result.begin() + result.size() / 2, mid);
    cout << result << "\n";

    return 0;
}

3. 소감

사실 맞왜틀 오래 했던 문제였다.
인터넷에 공개된 TC나 내가 생각한 TC는 다 맞는데 자꾸 틀렸었는데
로직은 다 짰는데 cnt >= 2 해당 if문에서 잘못된 if문을 작성했었다.
바로 고치긴 했다.
어쨌든 쉬운 문제였다.

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