Palindrome이란? Two Pointers와 TypeScript로 팰린드롬 검사하기

Palindrome은 앞에서 읽든 뒤에서 읽든 동일한 문자열, 숫자 또는 시퀀스를 의미합니다.

예:

racecar
level
madam
1221

반면:

hello
algorithm
1234

는 Palindrome이 아닙니다.

이 문제는 Two Pointers를 배우기에 매우 좋은 기본 문자열 문제입니다.

문자열을 뒤집는 방법

가장 간단한 해결 방법은 문자열을 Reverse한 뒤 원본과 비교하는 것입니다.

function isPalindrome(value: string): boolean {
  return value === value.split("").reverse().join("");
}

복잡도는:

Time: O(n)
Space: O(n)

입니다.

Two Pointers 방법

더 효율적인 방법은 양 끝에 Pointer를 두는 것입니다.

r a c e c a r
↑           ↑
L           R

두 문자가 같으면 가운데 방향으로 이동합니다.

function isPalindrome(value: string): boolean {
  let left = 0;
  let right = value.length - 1;

  while (left < right) {
    if (value[left] !== value[right]) {
      return false;
    }

    left++;
    right--;
  }

  return true;
}

복잡도:

Time: O(n)
Space: O(1)

공백과 특수문자 무시하기

대표적인 예:

A man, a plan, a canal: Panama

소문자로 바꾸고 문자가 아닌 항목을 제거하면:

amanaplanacanalpanama

가 되어 Palindrome임을 확인할 수 있습니다.

추가 문자열을 만들지 않고 Pointer가 이동하면서 특수문자를 Skip할 수도 있습니다.

숫자 Palindrome

121
1221
4554

같은 숫자도 Palindrome입니다.

숫자를 String으로 변환하거나 수학적으로 자리수를 뒤집어 검사할 수 있습니다.

function isNumberPalindrome(value: number): boolean {
  if (value < 0) return false;

  const original = value;
  let reversed = 0;

  while (value > 0) {
    const digit = value % 10;
    reversed = reversed * 10 + digit;
    value = Math.floor(value / 10);
  }

  return original === reversed;
}

Recursion

양 끝 문자를 비교하고 내부 범위를 Recursive하게 검사할 수도 있습니다.

시간은 O(n)이지만 Call Stack 때문에 추가 공간은 O(n) 정도가 필요합니다.

따라서 일반적으로 반복문을 이용한 Two Pointers가 더 효율적입니다.

Almost Palindrome

자주 나오는 확장 문제는 다음과 같습니다.

최대 한 문자를 삭제하여 Palindrome을 만들 수 있는가?

첫 mismatch에서 왼쪽 문자 또는 오른쪽 문자를 하나 Skip한 뒤 남은 범위가 Palindrome인지 검사할 수 있습니다.

관련 알고리즘 문제

Palindrome 개념은 다음 문제의 기반이 됩니다.

• Longest Palindromic Substring
• Palindromic Subsequence
• Palindrome Partitioning
• Minimum Insertions
• Valid Palindrome

Two Pointers의 중요성

Two Pointers는 다음 문제에서도 자주 사용됩니다.

• Pair Sum
• Remove Duplicates
• Partitioning
• Array Merge
• Container With Most Water

따라서 Palindrome은 이 패턴을 익히는 좋은 시작점입니다.

대소문자

Level이 Palindrome인지 여부는 규칙에 따라 다릅니다.

Case-sensitive 비교에서는 L과 l이 다르지만 lowercase로 정규화하면 level이 됩니다.

기술 면접 문제

흔한 문제는 공백, 특수문자, 대소문자를 무시하고 Palindrome인지 검사하는 것입니다.

좋은 해결 방식은:

Two Pointers
Skip invalid characters
Case-insensitive comparison

이며:

Time: O(n)
Space: O(1)

을 달성할 수 있습니다.

Edge Cases

""        → true
"a"       → true
"aa"      → true
"ab"      → false
"racecar" → true

정리

Palindrome은 양방향에서 동일하게 읽히는 시퀀스입니다.

표준 알고리즘은 Two Pointers이며:

Time Complexity: O(n)
Space Complexity: O(1)

입니다.

이 문제는 단순하지만 대칭 비교, Two Pointers, 문자열 정규화, Edge Case 처리와 같은 중요한 알고리즘 사고방식을 익히는 데 매우 유용합니다.