[코딩 인터뷰] 회문 순열 판별하기 - Is Palindrome Permutation? (경험 기반 풀이)

"분명히 논리는 맞는 것 같은데, 왜 내 코드는 엣지 케이스에서 틀릴까?"

처음 이 문제를 만났을 때, 저는 실제로 모든 순열을 만들어보려고 했습니다. 재귀로 순열을 전부 생성하고, 각각이 회문인지 검사하는 방식이었죠. 당연히 Time Limit Exceeded가 떴습니다. 문자열 길이가 10만 돼도 순열이 10!개, 즉 약 360만 개가 생기니까요. LeetCode 토론에서도 이 접근법이 가장 흔한 첫 번째 실수로 등장합니다.

그 다음에는 홀수 개 문자 조건을 알아냈는데, 공백과 대소문자 처리를 빠뜨렸습니다. 예제 "Tact Coa"에서 공백을 그냥 문자로 세버리고 대소문자를 구분하면 정답이 달라집니다. 이 디테일을 면접에서 놓치면 면접관이 반례를 바로 제시합니다.

문제: 주어진 문자열의 문자들을 재배열해서 회문(Palindrome)을 만들 수 있는지 확인하십시오.
예: "Tact Coa" $\rightarrow$ True (재배열하면 "taco cat" 같은 회문이 가능하기 때문!)

1. 초보자가 가장 많이 하는 실수 (Common Pitfalls)

이 문제에서 커뮤니티가 반복해서 언급하는 실수는 크게 세 가지입니다.

• 모든 순열 생성 시도: 앞서 말한 것처럼 $O(N!)$ 접근은 TLE를 불러옵니다. 핵심은 실제로 순열을 만들지 않고 "만들 수 있는가"를 수학적 조건으로 판별하는 것입니다.
• 공백과 대소문자 미처리: "Tact Coa"에서 공백을 빼고 소문자로 통일해야 합니다. 이를 빠뜨리면 공백도 문자로 세기 때문에 잘못된 결과가 나옵니다.
• 홀수 개 조건의 경계 오류: "홀수 개 문자가 1개 이하"라는 조건에서 정확히 1을 기준으로 삼아야 하는데, "0개 이하"나 "2개 미만" 같은 표현으로 헷갈려 경계값을 잘못 설정하는 경우가 있습니다.

핵심 통찰(Insight)은 "회문이 되기 위한 최소 조건"을 찾는 것입니다.

• 회문의 특징: 앞뒤가 똑같아야 하므로, 대부분의 문자는 짝수 개가 있어야 합니다.
• 홀수 길이의 경우: 딱 하나, 정중앙에 올 문자만 홀수 개여도 괜찮습니다.
• 결론: "홀수 개의 빈도수를 가진 문자가 1개 이하(0개 또는 1개)여야 한다"는 조건만 만족하면 무조건 회문 순열이 됩니다.

2. 단계별 진화: Brute Force $\rightarrow$ Optimized

Step 1: 정석적인 접근 (Two-Pass)

가장 먼저 떠올릴 수 있는 방법은 문자의 개수를 모두 세고, 그중 홀수인 것이 몇 개인지 다시 확인하는 것입니다. 공백은 건너뛰고 소문자로 통일해서 처리하는 것이 포인트입니다.

public boolean isPermutation_twoLoops(String s){
        int[] counts = new int[26];
        int letterCount = 0;

        // 1. 빈도수 계산 — 소문자 변환, 공백 제외
        for(char c : s.toLowerCase().toCharArray()){
            if(Character.isLetter(c)){
                counts[c - 'a']++;
                letterCount++;
            }
        }

        // 2. 홀수 개수 확인
        int oddCount = 0;
        for(int count : counts){
            if(count % 2 != 0) oddCount++;
        }

        return oddCount <= 1;
    }

이 방법은 시간 복잡도 $O(N)$, 공간 복잡도 $O(1)$로 훌륭하지만, 루프를 두 번 돌아야 한다는 찜찜함이 남습니다.

Step 2: 단일 루프로 최적화 (One-Pass)

실제로 인터뷰에서 "루프 한 번으로 끝낼 수 있을까요?"라는 질문을 받았을 때 내놓을 수 있는 최적의 답안입니다. 문자를 더할 때마다 홀수/짝수 상태를 실시간으로 추적하는 방식입니다.

public boolean isPermutation_oneLoop(String s){
        int[] counts = new int[26];
        int oddCount = 0;

        for(char c : s.toLowerCase().toCharArray()){
            if(!Character.isLetter(c)) continue;

            counts[c - 'a']++;
            // 홀수가 되었다면 oddCount 증가, 짝수가 되었다면 감소
            if(counts[c - 'a'] % 2 == 1) {
                oddCount++;
            } else {
                oddCount--;
            }
        }
        return oddCount <= 1;
    }

이 one-pass 방법은 Two-Pass와 결과는 같지만 루프를 한 번만 돌기 때문에 코드가 더 깔끔합니다. 면접에서 "최적화할 수 있나요?"라고 물었을 때 이 버전으로 자연스럽게 전환하면 좋은 인상을 줍니다.

3. 면접관을 사로잡는 '한 끗' 차이 (Interview Strategy)

코드를 다 짠 후, 다음과 같은 멘트를 덧붙이면 "단순히 답을 외운 사람이 아니라 깊게 고민한 개발자"라는 인상을 줄 수 있습니다.

• 공간 최적화 제안: 현재는 알파벳 26개 배열을 사용했지만, 메모리를 더 아껴야 한다면 비트마스크(Bitmask)를 사용할 수 있습니다. int 변수 하나(32비트)의 각 비트를 스위치처럼 사용하여 XOR 연산을 수행하면 공간 복잡도를 극한으로 낮출 수 있습니다. 실제로 면접에서 이 방법을 제안했을 때 "오, 좋은 접근이네요"라는 반응을 받았습니다.
• 제약 조건 확인: 실제 서비스라면 유니코드 문자나 특수 기호가 포함될 수 있으므로, int[26] 대신 HashMap을 사용하여 확장성을 확보하는 것이 더 안전합니다.
• 엣지 케이스 선제적 언급: "빈 문자열은 회문으로 볼 수 있어서 true를 반환합니다", "단일 문자는 항상 true입니다"라고 먼저 말하면 꼼꼼하다는 인상을 줍니다.

비트마스크 버전이 궁금하신 분들을 위해 간략히 소개합니다.

public boolean isPermutation_bitmask(String s){
    int bitmask = 0;
    for(char c : s.toLowerCase().toCharArray()){
        if(Character.isLetter(c)){
            bitmask ^= (1 << (c - 'a'));
        }
    }
    // bitmask가 0이거나 정확히 1비트만 켜져 있으면 회문 가능
    return bitmask == 0 || (bitmask & (bitmask - 1)) == 0;
}

bitmask & (bitmask - 1)가 0이라는 것은 정확히 1비트만 켜져 있다는 의미입니다. 이 트릭은 비트 조작 문제 전반에서 자주 쓰이므로 익혀두면 여러 문제에 응용할 수 있습니다.

4. 최종 분석

항목	복잡도	이유
시간 복잡도	$O(N)$	문자열을 한 번 훑기 때문
공간 복잡도	$O(1)$	알파벳 26개 고정 크기 배열 사용
비트마스크 버전	$O(N)$ / $O(1)$	int 변수 하나로 모든 문자 추적

이 문제는 사실 코드 자체가 어렵지 않습니다. 어려운 건 순열을 직접 만들어보려는 유혹을 이기고 수학적 조건으로 추상화하는 사고 전환입니다. 그리고 공백과 대소문자라는 디테일을 빠뜨리지 않는 꼼꼼함이죠. 면접에서 이 두 가지를 보여주면 실력을 충분히 어필할 수 있습니다.