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

코드

#include <iostream>
#include <string>

using namespace std;

string s, res;
int charCount[26];

void constructPalindrome(int oddIdx) {
    // 절반 부분 추가
    for(int i = 0; i < 26; i++) {
        int halfCount = charCount[i] / 2;
        res += string(halfCount, char(i + 'A'));
    }
    // 가운데 문자 추가 (홀수 길이의 경우)
    if (oddIdx != -1) {
        res += char(oddIdx + 'A');
    }
    // 뒤쪽 부분 추가
    for(int i = 25; i >= 0; i--) {
        int halfCount = charCount[i] / 2;
        res += string(halfCount, char(i + 'A'));
    }
}

int main() {
    cin >> s;
    int oddCount = 0, oddIdx = -1, len = s.length();

    // 각 문자의 개수 카운트
    for(int i = 0; i < len; i++) {
        charCount[s[i] - 'A']++;
    }

    // 홀수 개수 찾기
    for(int i = 0; i < 26; i++) {
        if (charCount[i] % 2 == 1) {
            oddCount++;
            oddIdx = i;
        }
    }

    // 홀수 길이인 경우 홀수 문자 1개만 허용
    // 짝수 길이인 경우 홀수 문자가 없어야 함
    if ((len % 2 == 1 && oddCount > 1) || (len % 2 == 0 && oddCount > 0)) {
        res = "I'm Sorry Hansoo";
    } else {
        if (oddIdx != -1) charCount[oddIdx]--;
        constructPalindrome(oddIdx);
    }

    cout << res << '\n';
    return 0;
}

풀이

팰린드롬을 만들 경우를 분석해봤다. 우선 길이가 짝수인 경우에는 홀수 개인 알파벳이 있으면 안된다. 그리고 길이가 홀수인 경우에는 홀수 개인 알파뱃은 1개여야 한다. 이 분석을 토대로 조건문을 구성했고, 팰린드롬 구성 시에는 사전순으로 빠른 것을 출력해야하기 때문에 앞에서부터 값이 있으면 절반 부분을 더해주었다. 그리고 홀수가 존재하는 경우에, 나머지 절반을 더하기 전에 홀수인 알파뱃을 붙여주었다.