C++로 회문 순열 만들기: 제거해야 할 최소 문자 수 구하기

문제 정의

문자열 S가 주어졌을 때, 문자열 S의 어떤 순열이라도 회문(palindrome)이 될 수 있도록 제거해야 하는 문자의 최소 개수를 구하는 것이 목표입니다.

예시

예를 들어 str = "abcdba"인 경우, 문자 1개만 제거하면 됩니다. 즉 'c' 또는 'd' 중 하나를 없애면 나머지 문자들로 회문을 만들 수 있습니다.

접근 방법 및 알고리즘

회문의 성질을 이용하면 간단하게 해결할 수 있습니다.

1. 회문은 길이에 따라 두 가지 유형으로 나뉩니다. 짝수 길이 회문과 홀수 길이 회문입니다.
2. 짝수 길이 회문은 모든 문자가 반드시 짝수 번 등장해야 합니다.
3. 홀수 길이 회문 역시 모든 문자가 짝수 번 등장해야 하며, 단 하나의 문자만 홀수 번 등장할 수 있습니다(정중앙에 위치하는 문자).

따라서 다음과 같은 절차로 답을 구할 수 있습니다.

1. 각 문자의 등장 빈도를 계산합니다.
2. 빈도가 홀수인 문자의 개수를 셉니다.
3. 결괏값은 (홀수 빈도를 가진 문자의 총 개수) − 1입니다. 단, 홀수 빈도 문자가 없다면 결과는 0입니다.

왜 1을 빼는 걸까요? 홀수 길이 회문은 가운데에 위치할 문자 하나를 허용하기 때문에, 홀수 빈도 문자 중 하나는 남겨두고 나머지만 제거하면 되기 때문입니다.

C++ 구현 예제

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

int minCharactersRemoved(string str) {
    int hash[MAX] = {0};
    // 각 문자의 등장 빈도 계산
    for (int i = 0; str[i]; ++i) {
        hash[str[i] - 'a']++;
    }
    // 홀수 빈도를 가진 문자 개수 세기
    int cnt = 0;
    for (int i = 0; i < MAX; ++i) {
        if (hash[i] & 1) {
            ++cnt;
        }
    }
    return (cnt == 0) ? 0 : (cnt - 1);
}

int main() {
    string str = "abcdba";
    cout << "Minimum characters to be removed = " <<
        minCharactersRemoved(str) << endl;
    return 0;
}

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

실행 결과

Minimum characters to be removed = 1

복잡도 분석

• 시간 복잡도: O(N) — 문자열을 한 번 순회하여 빈도를 계산하고, 26개 알파벳에 대해 한 번 더 확인합니다.
• 공간 복잡도: O(1) — 크기가 26으로 고정된 해시 배열만 사용합니다.