[C++][백준 1213] 팰린드롬 만들기

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

제출코드

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

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

    string name;
    int count[26] = {};
    vector<char> res;
    char mid = 0;
    cin >> name;

    for (int i = 0; i < name.length(); i++)
        count[name[i] - 'A']++;

    for (int i = 0; i < 26; i++)
    {
        if (count[i] % 2 == 1)
        {
            if (mid != 0 || name.length() % 2 == 0)
            {
                cout << "I'm Sorry Hansoo" << '\n';
                return 0;
            }
            mid = i + 'A';
        }
    }

    for (int i = 0; i < 26; i++)
    {
        if (i + 'A' == mid && count[i] == 1) continue;
        for (int j = 0; j < count[i] / 2; j++)
            res.push_back(i + 'A');
    }

    for (int i = 0; i < res.size(); i++)
        cout << res[i];

    if (mid != 0)
        cout << mid;

    for (int i = res.size() - 1; i > -1; i--)
        cout << res[i];
}

팰린드롬이란 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 말한다고 한다

 

이를 만족하기 위해서는

1. 주어진 이름의 길이가 짝수이고, 중복되는 알파벳들 또한 전부 짝수인 경우

2. 주어진 이름의 길이가 홀수이고, 중복되는 알파벳 중 1개 이하가 홀수인 경우

여야 한다

 

우선 map<char, int>로 중복되는 알파벳 개수를 체크했다

그리고 for문을 돌면서 count된 수를 체크하여

1. count가 홀수이고, 이름의 길이가 짝수인 경우

2. count가 홀수이고, 이미 홀수인 다른 알파벳이 존재한 경우

불가능 문장을 출력하고 끝내도록 했다

 

중간에 오는 글자를 뜻하는 mid 변수에는 초기값으로 0을 넣어두고, mid값이 0이 아니라면 이미 다른 홀수인 알파벳이 존재한다는 의미이므로 불가능을 출력했다

 

그리고 남은 알파벳은 1개(혹은 0개) 제외하고는 전부 짝수이므로 절반에 해당되는 만큼 vector에 집어넣고

출력할 때는 앞에서 뒤로, 뒤에서 앞으로 두 번 출력하는 방식으로 대칭을 이루도록 하였다

(마찬가지로 mid가 초기값이 아닌 경우 중간에 오는 글자가 있다는 뜻이므로 중간에 출력하도록 하였다)

 

이후 다른 사람의 정답을 보다가 뒤늦게 정답이 여러 개일 경우 사전순으로 앞서는 것을 출력하라는 조건을 보았다...

다만 애초에 vector에 추가할 때 A부터 중복되는 수를 전부 추가하고 다음 알파벳으로 넘어가기 때문에 자동으로 해당 조건을 만족하고 있었다

이번 문제는 얻어걸렸으나 앞으론 좀 더 꼼꼼하게 문제를 읽자