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

문제

1213번: 팰린드롬 만들기

풀이

그리디, 문자열, 구현

 

홀수개로 입력된 알파벳의 개수에 따라 결과가 달라진다. 

1. 홀수개로 입력된 알파벳이 2개 이상이라면, 팰린드롬을 만들 수 없다. 
2. 홀수개로 입력된 알파벳이 1개라면, 팰린드롬의 가운데 문자가 해당 알파벳이 된다.
3. 홀수개로 입력된 알파벳이 0개라면, 입력된 문자의 개수가 짝수이므로, 가운데 문자가 없다. 

사전순으로 가장 앞서는 문자열을 출력해야 한다. 결과 문자열 앞의 문자열은 A부터 Z까지 입력된 횟수의 절반 개수만큼 출력하고, 뒤의 문자열은 Z부터 A까지 입력된 횟수의 절반 개수만큼 출력한다. 만약 홀수개로 입력된 알파벳이 있다면 그 사이에 출력하여 팰린드롬을 만든다. 

// A부터 Z까지 입력된 횟수의 절반을 출력
for (int i = 0; i < 26; ++i)
{
    for (int j = 0; j < alphabet[i] / 2; ++j)
    {
        cout << (char)('A' + i);
    }
}

// 홀수개로 입력된 알파벳은 중간에 출력
if (odd_count == 1)
{
    cout << (char)('A' + odd_index);
}

// Z부터 A까지 입력된 횟수의 절반을 출력
for (int i = 25; i >= 0; --i)
{
    for (int j = 0; j < alphabet[i] / 2; ++j)
    {
        cout << (char)('A' + i);
    }
}

코드

#include <iostream>
#include <string>

using namespace std;

char alphabet[26];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    string s;
    cin >> s;

    for (int i = 0; i < s.size(); ++i)
    {
        alphabet[s[i] - 'A']++;
    }

    int odd_count = 0;
    int odd_index = 0;
    for (int i = 0; i < 26; ++i)
    {
        if (alphabet[i] % 2 == 1)
        {
            odd_count++;
            odd_index = i;
        }
    }

    // 홀수로 입력된 알파벳이 2개 이상이라면 펠린드롬을 만들 수 없다.
    if (odd_count >= 2)
    {
        cout << "I'm Sorry Hansoo";
        return 0;
    }

    // A부터 Z까지 입력된 횟수의 절반을 출력
    for (int i = 0; i < 26; ++i)
    {
        for (int j = 0; j < alphabet[i] / 2; ++j)
        {
            cout << (char)('A' + i);
        }
    }

    // 홀수개로 입력된 알파벳은 중간에 출력
    if (odd_count == 1)
    {
        cout << (char)('A' + odd_index);
    }

    // Z부터 A까지 입력된 횟수의 절반을 출력
    for (int i = 25; i >= 0; --i)
    {
        for (int j = 0; j < alphabet[i] / 2; ++j)
        {
            cout << (char)('A' + i);
        }
    }

    return 0;
}