회문 순열

회문 순열이란?

주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라는 문제가 자주 나온다.

회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며,

순셜이란 문자열을 재배치하는 것을 뜻한다.

회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다.

 

이 문제를 풀기 위해서는 문자열이 회문의 순열이 된다는 것이 무슨 뜻인지 알아야 한다.

즉, 이런 문자열이 되기 위한 정의적 세부 특징이 무엇인지 질문하는 것과 같다.

회문은 앞으로 읽으나 뒤로 읽으나 같은 문자열을 뜻한다.

즉, 해당 문자열이 회문의 순열인지 판단하기 위해서는

어느 방향으로 읽어도 같은 문자열이 되도록 만들 수 있는지 알아야 한다.

 

 어느 방향으로 읽어도 같은 문자열이 되기 위해서는 어떤 조건이 필요할까?

거의 모든 문자가 각각 짝수 개 존재해서 절반은 왼쪽에 나머지 절반은 오른쪽에 놓을 수 있으면 된다.

단 한 개의 문자만 홀수 개여야 한다. 그래야 해당 문자를 중간에 놓고 나머지를 절반씩 왼쪽 오른쪽에 나눠 놓을 수 있다.

 예를 들어 tractcoapapa는 t가 2개, a가 4개, c가 2개, p가 2개 o가 1개 있으므로 회문의 순열이 된다.

가능한 회문에서 o는 항상 가운데 있어야 한다.

 좀 더 정확히 말하자면 문자열의 길이가 짝수일 때는 모든 문자의 개수가 반드시 짝수여야 한다.

만약 문자열의 길이가 홀수라면 문자 하나는 홀수개 존재해도 괜찮다.

 

물론 짝수 길이의 문자열에서 개수가 홀수인 문자가 단 한 개 존재할 순 없다.

존재한다면 짝수 길이가 아니기 때문이다.

홀수 + 많은 짝수들 = 홀수 

 

마찬가지로 홀수 길이 문자열에 모든 문자의 개수가 짝수 개일 수 없다 (작수를 합하면 짝수가 된다.)

따라서 회문이 되기 위해서는 홀수인 문자가 하나여야 한다는 것은 회문을 설명하기에 충분한 사실이다.

이 문장으로 짝수와 홀수 두 가지 경우를 모두 설명할 수 있기 때문이다.

 

 

이 알고리즘의 구현은 꽤나 간단하다.

해시테이블을 사용해서 각 문자가 몇 번이나 등장했는지 센다.

그 다음엔 해시테이블을 훑어가며 홀수 문자가 한 개 이상인지 확인한다.

 

#include <string>
#include <vector>
#include <cctype> // tolower, isalpha

// 문자의 a~z 인덱스를 리턴 (a=0, b=1, ... z=25), 알파벳이 아니면 -1 리턴
int getCharNumber(char c) {
    c = std::tolower(c);
    if ('a' <= c && c <= 'z') {
        return c - 'a';
    }
    return -1;
}

// 각 문자의 등장 횟수를 배열로 기록
std::vector<int> buildCharFrequencyTable(const std::string& phrase) {
    std::vector<int> table(26, 0); // a~z
    for (char c : phrase) {
        int idx = getCharNumber(c);
        if (idx != -1) {
            table[idx]++;
        }
    }
    return table;
}

// 홀수 개수 문자가 2개 이상인지 체크
bool checkMaxOneOdd(const std::vector<int>& table) {
    bool foundOdd = false;
    for (int count : table) {
        if (count % 2 == 1) {
            if (foundOdd) return false;
            foundOdd = true;
        }
    }
    return true;
}

// 회문 순열 판별 함수
bool isPermutationOfPalindrome(const std::string& phrase) {
    auto table = buildCharFrequencyTable(phrase);
    return checkMaxOneOdd(table);
}