[leetcode] Palindrome Number/ 팔린드롬 수, 배열 풀이 vs 공간 최적화 풀이

🌀 팔린드롬(Palindrome) 수란?

팔린드롬(Palindrome)은 앞에서 읽든 뒤에서 읽든 똑같은 수를 말합니다.

예를 들어:

• 121 → 팔린드롬 ✅
• 12321 → 팔린드롬 ✅
• 123 → 팔린드롬 ❌
• -121 → 음수는 회문이 아님 ❌

---

📌 문제 설명 (LeetCode 9. Palindrome Number)

주어진 정수 x가 팔린드롬인지 확인하는 함수를 작성하시오.
단, 음수는 팔린드롬이 아니며, 숫자를 문자열로 바꾸지 않고 해결하길 권장합니다.

 

// Example 1:
Input: x = 121
Output: true

// Example 2:
Input: x = -121
Output: false

// Example 3:
Input: x = 10
Output: false

---

✅ 풀이 1: 배열을 이용한 직관적인 방법

💡 아이디어

1. 숫자의 각 자릿수를 배열에 담는다.
2. 배열의 앞쪽과 뒤쪽 값을 비교한다.
3. 한 쌍이라도 다르면 false, 모두 같으면 true.

💻 코드

var isPalindrome = function(x) {
    if (x < 0) return false;

    let arr = [];
    while (x > 0) {
        arr.push(x % 10);
        x = Math.floor(x / 10);
    }

    for (let i = 0; i < Math.floor(arr.length / 2); i++) {
        if (arr[i] !== arr[arr.length - 1 - i]) {
            return false;
        }
    }
    return true;
};​

 

⏱ 복잡도 분석

 

항목	복잡도
시간 복잡도	O(log x) → 자릿수만큼 반복
공간 복잡도	O(log x) → 배열에 자릿수 저장

---

✅ 풀이 2: 공간을 아끼는 최적화 방법 (공간 O(1))

💡 아이디어

1. 숫자의 뒤 절반만 뒤집어서 앞 절반과 비교한다.
2. 예: 1221 → 앞 절반 12, 뒤집은 절반 21
3. 두 수가 같으면 팔린드롬

💻 코드

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

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

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

⏱ 복잡도 분석

 

항목	복잡도
시간 복잡도	O(log x)
공간 복잡도	O(1) → 추가 배열 없이 계산

---

🔍 배열 풀이 vs 공간 최적화 비교표

 

항목	배열 풀이공간	최적화 풀이
직관성	✅ 높음 (이해 쉬움)	⚠️ 조금 더 복잡
공간 효율성	❌ O(log x)	✅ O(1)
구현 난이도	쉬움	약간 중급
면접 어필	기본 풀이	💡 최적화 전략 제시 가능

---

📝 마무리

• 팔린드롬 수는 "문자열처럼 보지만 숫자로 풀어야 하는" 대표적인 문제입니다.
• 배열을 활용한 풀이로 쉽게 접근할 수 있고,
  공간 O(1) 풀이로 최적화를 고민할 수 있습니다.
• 두 가지 풀이법 모두 익혀두면 코딩테스트와 면접에 모두 유리합니다!