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

박상혁·2026년 5월 22일

PS

목록 보기

11/95

이번에는 백준 1213번 팰린드롬 만들기 문제를 풀어보았습니다.

이 문제는 주어진 문자열의 알파벳 순서를 적절히 바꾸어 팰린드롬을 만들 수 있는지 확인하고, 가능하다면 그 결과를 출력하는 문제입니다.

단순히 문자열을 뒤집어 비교하는 문제가 아니라, 각 알파벳의 개수를 바탕으로 팰린드롬을 만들 수 있는지 판단해야 했습니다.

문제 설명

알파벳 대문자로 이루어진 문자열이 주어집니다.

이 문자열의 문자 순서를 바꾸어 팰린드롬을 만들 수 있으면 그 결과를 출력하고, 만들 수 없다면 "I'm Sorry Hansoo"를 출력하면 됩니다.

또한 가능한 정답이 여러 개라면 사전순으로 가장 앞서는 문자열을 출력해야 합니다.

풀이 아이디어

팰린드롬은 앞뒤가 대칭인 문자열입니다.

그래서 각 알파벳의 개수를 기준으로 보면 중요한 조건이 하나 나옵니다.

짝수 개수의 알파벳은 양쪽에 똑같이 배치할 수 있다.
홀수 개수의 알파벳은 가운데에 하나만 올 수 있다.

즉, 홀수 개수의 알파벳이 두 개 이상이면 팰린드롬을 만들 수 없습니다.

그래서 먼저 각 알파벳의 개수를 세고, 홀수 개수의 알파벳이 몇 개인지를 확인했습니다.

그 다음에는

홀수 개수의 알파벳이 있다면 가운데에 먼저 넣고
나머지 알파벳들을 양쪽에 대칭으로 붙이는 방식

으로 결과 문자열을 만들었습니다.

코드

#include <bits/stdc++.h>
using namespace std;

int cnt[26];
string input;
int odd_num = -1;
int odd_count;

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

    cin >> input;

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

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

    string result = "";

    if (odd_count > 1) {
        cout << "I'm Sorry Hansoo";
    } else if (odd_count == 1) {
        result += (char)(odd_num + 'A');
    }

    for (int i = 25; i >= 0; i--) {
        for (int j = 0; j < (cnt[i] / 2); j++) {
            result = result + (char)(i + 'A');
            result = (char)(i + 'A') + result;
        }
    }

    cout << result << "\n";
    return 0;
}

풀이 흐름

입력 문자열의 각 알파벳 개수를 배열에 저장한다.
홀수 개수의 알파벳이 몇 개인지 센다.
홀수 개수가 2개 이상이면 팰린드롬을 만들 수 없으므로 "I'm Sorry Hansoo"를 출력한다.
홀수 개수가 1개라면 그 알파벳을 결과 문자열의 가운데에 먼저 넣는다.
각 알파벳을 (개수 / 2)만큼 결과 문자열의 앞뒤에 붙인다.
완성된 문자열을 출력한다.

구현 포인트

1. 홀수 개수의 알파벳은 하나만 가능

팰린드롬은 좌우 대칭이므로, 홀수 개수의 문자가 여러 개 있으면 가운데에 둘 수가 없습니다.

그래서 먼저 홀수 개수의 알파벳이 몇 개인지 세고,

그 수가 2 이상이면 바로 불가능한 경우로 처리했습니다.

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

2. 홀수 개수의 알파벳은 가운데에 먼저 배치

홀수 개수의 알파벳이 하나 존재한다면, 그 문자는 팰린드롬의 정중앙에 와야 합니다.

그래서 결과 문자열에 먼저 추가했습니다.

if (odd_count == 1) {
    result += (char)(odd_num + 'A');
}

3. 나머지는 절반만큼 앞뒤에 붙이기

짝수 개수의 알파벳은 절반은 왼쪽, 절반은 오른쪽에 배치하면 됩니다.

홀수 개수의 경우도 cnt[i] / 2를 하면 가운데에 들어갈 하나를 제외한 나머지 절반만 계산되므로 그대로 사용할 수 있습니다.

for (int i = 25; i >= 0; i--) {
    for (int j = 0; j < (cnt[i] / 2); j++) {
        result = result + (char)(i + 'A');
        result = (char)(i + 'A') + result;
    }
}