백준 1213번 팰린드롬 만들기

문제 링크입니다: https://www.acmicpc.net/problem/1213

문자열의 최대 길이가 50이기 때문에 브루트 포스(Brute Force)로 접근해도 무방한 문제였습니다.

팰린드롬을 만들 수 있는 조건은 아래와 같이 두 종류가 있습니다.

1. 모든 문자가 짝수개 있다.

2. 하나의 문자가 홀수개 있고 나머지 문자들이 짝수개 있다.

1번의 경우 문자열을 사전순으로 정렬한 상태에서 새로운 문자열에 (각 문자의 개수의 반)만큼 문자열을 추가해주고 출력한 뒤 거꾸로 출력해주면 팰린드롬이 완성됩니다.

2번의 경우 1번의 경우와 똑같은데 거꾸로 출력해주기 전에 홀수개였던 문자 하나를 추가해주고 거꾸로 출력해주면 됩니다!

#include <iostream>

#include <vector>

#include <string>

using namespace std;

 

int alphabet[26];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        string s;

        cin >> s;

 

        for (int i = 0; i < s.length(); i++)

                 alphabet[s[i] - 'A']++;

 

        vector<pair<char, int>> v;

        vector<char> middle;

        bool flag = false;

        for (int i = 0; i < 26; i++)

                 //홀수개인 문자가 2개 이상일 수 없습니다.

                 if (alphabet[i] % 2 && flag)

                 {

                         cout << "I'm Sorry Hansoo\n";

                         return 0;

                 }

                 else if (alphabet[i] % 2 && !flag)

                 {

                         v.push_back({ i + 'A', alphabet[i] - 1 });

                         middle.push_back(i + 'A');

                         flag = true;

                 }

                 else

                         v.push_back({ i + 'A', alphabet[i] });

 

        string result;

        //사전순으로 정렬한 상태에서 반씩 추가해주고

        for (int i = 0; i < v.size(); i++)

                 for (int j = 0; j < (v[i].second / 2); j++)

                         result += v[i].first;

 

        for (int i = 0; i < result.size(); i++)

                 cout << result[i];

        if(middle.size())

                 cout << middle[0];

        for (int i = result.size() - 1; i >= 0; i--)

                 cout << result[i];

        cout << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~