백준 1213 - 팰린드롬 만들기

문제 설명

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 주어진 문자열을 재배열해 만들 수 있는 팰린드롬 중 사전순으로 가장 빠른 문자열을 출력하면 된다.

 

우선 팰린드롬을 만들 수 있는 조건이 있다.

홀수인 문자의 개수가 1개 이하일 때만 팰린드롬을 만들 수 있다. 

홀수인 문자가 1개일 때만 가운데 문자를 배치한 후 좌우 대칭으로 문자를 배치할 수 있기 때문이다.

 

따라서 모든 문자의 개수를 세고 홀수인 문자가 1개 초과라면 종료한다.

for (int i = 0; i < str.length(); i++)
{
    spellCnt[str[i] - 'A']++;
}

int odd = 0;
char oddChar = ' ';
for (auto spell = 'A'; spell <= 'Z'; spell++)
{
    auto cnt = spellCnt[spell - 'A'];
    if (cnt % 2 == 1)
    {
        odd++;
        oddChar = spell;
    }
}

if (odd > 1)
{
    cout << "I'm Sorry Hansoo";
    return 0;
}

 

이제 팰린드롬은 만들 수 있기 때문에 모든 문자의 절반을 차례로 더해가며 팰린드롬의 왼쪽을 구성한다.

이후 만약 홀수인 문자가 있다면 추가하고 나머지 절반을 뒤집어 더해주면 된다.

string ans;
for (auto spell = 'A'; spell <= 'Z'; spell++)
{
    auto cnt = spellCnt[spell - 'A'];
    auto half = cnt / 2;

    for (int i = 0; i < half; i++)
    {
        ans += spell;
    }
}

auto rev = ans;
reverse(rev.begin(), rev.end());

if (odd == 1)
{
    ans += oddChar;
}
ans += rev;

cout << ans;

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321

using namespace std;
string str;
vector<int> spellCnt(26, 0);

int main()
{
    INPUT_OPTIMIZE;

    cin >> str;

    for (int i = 0; i < str.length(); i++)
    {
        spellCnt[str[i] - 'A']++;
    }

    int odd = 0;
    char oddChar = ' ';
    for (auto spell = 'A'; spell <= 'Z'; spell++)
    {
        auto cnt = spellCnt[spell - 'A'];
        if (cnt % 2 == 1)
        {
            odd++;
            oddChar = spell;
        }
    }

    if (odd > 1)
    {
        cout << "I'm Sorry Hansoo";
        return 0;
    }

    string ans;
    for (auto spell = 'A'; spell <= 'Z'; spell++)
    {
        auto cnt = spellCnt[spell - 'A'];
        auto half = cnt / 2;

        for (int i = 0; i < half; i++)
        {
            ans += spell;
        }
    }

    auto rev = ans;
    reverse(rev.begin(), rev.end());

    if (odd == 1)
    {
        ans += oddChar;
    }
    ans += rev;

    cout << ans;

    return 0;
}

---