[알고리즘][문자열] 팰린드롬(Palindrome)

 

✅ 팰린드롬(Palindrome) 정리

1. 정의

팰린드롬이란 앞에서 읽으나 뒤에서 읽으나 같은 문자열을 말한다.
문자, 숫자, 문장 모두 해당할 수 있으며, 보통 공백·기호·대소문자를 무시한다.

예시:

• "madam" → ✅
• "racecar" → ✅
• "A man, a plan, a canal, Panama" → ✅ (전처리 후)
• "hello" → ❌

---

2. 조건

팰린드롬이 되기 위한 조건:

• 좌우가 대칭이어야 함
• 대소문자 구분 없이 비교
• 특수문자, 공백 무시 가능

---

3. 주요 활용 사례

• 문자열 유효성 검사
• 자연어 처리 / 텍스트 마이닝
• 회문 관련 알고리즘 (최장 회문 부분 문자열 등)
• 인터뷰/프로그래밍 대회

---

4. 구현

✅ Java: 투 포인터 방식

public boolean isPalindrome(String str) {
    str = str.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();  // 전처리
    int left = 0, right = str.length() - 1;

    while (left < right) {
        if (str.charAt(left++) != str.charAt(right--)) {
            return false;
        }
    }
    return true;
}

---

✅ C 언어 구현

#include <stdio.h>
#include <string.h>
#include <ctype.h>

void cleanString(const char* src, char* dest) {
    int j = 0;
    for (int i = 0; src[i]; i++) {
        if (isalnum(src[i])) {
            dest[j++] = tolower(src[i]);
        }
    }
    dest[j] = '\0';
}

int isPalindrome(const char* str) {
    char cleaned[1000];
    cleanString(str, cleaned);
    int left = 0, right = strlen(cleaned) - 1;

    while (left < right) {
        if (cleaned[left++] != cleaned[right--]) return 0;
    }
    return 1;
}

---

✅ Python 구현

def is_palindrome(s: str) -> bool:
    # 전처리: 알파벳/숫자만 남기고 소문자로 변환
    s = ''.join(c.lower() for c in s if c.isalnum())

    # 투포인터로 비교
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

# 테스트
print(is_palindrome("A man, a plan, a canal, Panama"))  # True
print(is_palindrome("hello"))  # False

 

---

5. 팁 & 주의사항

항목 설명

전처리 정규식	Java: replaceAll("[^a-zA-Z0-9]", "")Python: isalnum() 사용
대소문자 무시	Java: toLowerCase() C: tolower() Python: .lower()
문자열 비교	투 포인터 방식이 일반적이며 가장 효율적
Unicode 주의	한글 포함 시 정규화(NFC/NFD) 고려 필요 (Python unicodedata)