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

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

알고리즘 문제를 풀다 보면 정답 코드를 보고 "아, 쉽네"라고 생각하지만, 막상 빈 화면에서 짜려고 하면 null 처리나 공백, 대소문자 같은 디테일에서 막히는 경우가 많습니다. 특히 '회문 순열' 문제는 단순해 보이지만, '효율성'과 '예외 처리'라는 두 마리 토끼를 잡아야 하는 전형적인 인터뷰 문제입니다.

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

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

이 문제를 처음 접하면 많은 분이 "모든 순열을 다 만들어보고 회문인지 확인해야 하나?"라는 생각에 빠집니다. 하지만 그렇게 하면 시간 복잡도가 $O(N!)$이라는 어마어마한 숫자가 되어 바로 TLE(Time Limit Exceeded)를 만나게 됩니다.

여기서 핵심 통찰(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;
    }

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

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

• 공간 최적화 제안: 현재는 알파벳 26개 배열을 사용했지만, 메모리를 더 아껴야 한다면 비트마스크(Bitmask)를 사용할 수 있습니다. int 변수 하나(32비트)의 각 비트를 스위치처럼 사용하여 XOR 연산을 수행하면 공간 복잡도를 극한으로 낮출 수 있습니다.
• 제약 조건 확인: 실제 서비스라면 유니코드 문자나 특수 기호가 포함될 수 있으므로, int[26] 대신 HashMap을 사용하여 확장성을 확보하는 것이 더 안전합니다.

4. 최종 분석

항목	복잡도	이유
시간 복잡도	$O(N)$	문자열을 한 번 훑기 때문
공간 복잡도	$O(1)$	알파벳 26개 고정 크기 배열 사용