문제 설명

Palindrome Number - LeetCode

주어진 정수 x가 팰린드롬 수(Palindrome Number) 인지 판별하는 문제입니다.

✅ 팰린드롬(Palindrome)이란?

  • 앞에서 읽어도, 뒤에서 읽어도 같은 수
  • 예: 121, 1221, 12321 ✅
  • 예: 10, -121 ❌ (- 부호가 있으므로 불가능)

✅ 제약 조건

  • 음수는 팰린드롬이 될 수 없음 (부호가 다르므로)
  • 맨 끝이 0인 경우도 팰린드롬이 될 수 없음 (단, 0 자체는 가능)

해설

1️⃣ 문자열 변환 방식 (O(N), 추가 공간 필요)

  • 숫자를 문자열(str) 로 변환 후 거꾸로 뒤집어 비교
  • 시간 복잡도: O(N) (문자열 길이만큼 비교)
  • 공간 복잡도: O(N) (새로운 문자열 생성)

2️⃣ 숫자 연산 방식 (O(log N), 추가 공간 없이 해결) [추천]

  • 숫자를 뒤집어 원래 숫자와 비교
  • 추가 공간을 사용하지 않음 → 효율적
  • 시간 복잡도: O(log N) (숫자의 자릿수만큼 반복)
  • 공간 복잡도: O(1) (추가 배열 없음)

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def isPalindrome(x: int) -> bool:
    if x < 0 or (x % 10 == 0 and x != 0):  # 음수 또는 10, 100 같은 숫자 제외
        return False

    reversed_half = 0
    while x > reversed_half:  # 숫자의 절반만 뒤집기
        reversed_half = reversed_half * 10 + x % 10
        x //= 10  # 마지막 자리 제거

    return x == reversed_half or x == reversed_half // 10  # 짝수, 홀수 길이 비교

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

var isPalindrome = function(x) {
    if (x < 0 || (x % 10 === 0 && x !== 0)) return false;

    let reversedHalf = 0;
    while (x > reversedHalf) {
        reversedHalf = reversedHalf * 10 + x % 10;
        x = Math.floor(x / 10);
    }

    return x === reversedHalf || x === Math.floor(reversedHalf / 10);
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform