Palindrome Number — 문자열 없이 절반만 뒤집는 숫자 팰린드롬 판정

숫자 팰린드롬 판정, 어떤 문제인가요?

LeetCode 9번 문제는 이렇게 주어집니다.

정수 x가 주어졌을 때, x가 팰린드롬이면 true, 아니면 false를 반환합니다. 팰린드롬은 앞에서 읽은 값과 뒤에서 읽은 값이 같은 형태를 말합니다.

예시는 이렇습니다.

• x = 121 → true
• x = -121 → false
• x = 10 → false

제약은 다음과 같습니다.

• -2^31 <= x <= 2^31 - 1

문제의 follow-up은 정수를 문자열로 바꾸지 않고 풀 수 있는가입니다.

핵심은 숫자의 앞쪽 절반과 뒤집은 뒤쪽 절반이 같은지 비교하는 것입니다. 이 글에서는 가장 단순한 문자열 풀이부터, 전체 숫자 뒤집기, 그리고 오버플로우 걱정을 줄이는 절반 뒤집기 풀이까지 단계적으로 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

Phase 1. 문자열로 바꿔서 뒤집기

가장 먼저 떠올릴 수 있는 방법은 정수를 문자열로 바꾼 뒤, 문자열을 뒤집어 비교하는 것입니다.

fun isPalindrome(x: Int): Boolean {
    val s = x.toString()
    return s == s.reversed()
}

이 방식은 121을 "121"로 바꾸고, 뒤집은 문자열도 "121"인지 확인합니다. -121은 문자열이 "-121"이 되고, 뒤집으면 "121-"이므로 자연스럽게 false가 됩니다. 10은 "01"과 비교되므로 false입니다.

코드는 가장 짧고 실수할 여지도 적습니다. 하지만 문제의 follow-up이 "문자열 변환 없이 풀 수 있는가"이므로, 여기서 끝내기보다는 숫자 연산으로 바꿔 보는 것이 좋습니다.

시간 복잡도는 자릿수를 d라고 할 때 O(d), 공간 복잡도도 문자열을 만들기 때문에 O(d)입니다.

Phase 2. 숫자를 전부 뒤집어서 비교하기

문자열을 쓰지 않으려면 숫자의 마지막 자릿수를 하나씩 꺼내 새 숫자 뒤에 붙이면 됩니다.

예를 들어 121은 이렇게 뒤집습니다.

n = 121, reversed = 0
마지막 자리 1 → reversed = 1,   n = 12
마지막 자리 2 → reversed = 12,  n = 1
마지막 자리 1 → reversed = 121, n = 0

코드는 이렇게 됩니다.

fun isPalindrome(x: Int): Boolean {
    if (x < 0) return false

    var n = x
    var reversed = 0L

    while (n > 0) {
        val digit = n % 10
        reversed = reversed * 10 + digit
        n /= 10
    }

    return reversed == x.toLong()
}

음수는 먼저 false로 처리합니다. -121을 수학적으로 뒤집는다고 해도 부호가 뒤로 갈 수는 없기 때문입니다.

여기서 reversed를 Long으로 둔 이유가 중요합니다. 입력 x는 Int 범위 안에 있지만, 뒤집은 값은 Int 범위를 넘어갈 수 있습니다. 예를 들어 2147483647을 전부 뒤집으면 7463847412가 되어 Int에 담기지 않습니다.

이 풀이도 시간 복잡도는 O(d), 추가 공간은 O(1)입니다. 다만 전체 숫자를 뒤집기 때문에 언어에 따라 오버플로우를 의식해야 합니다. 그래서 더 좋은 방법은 절반만 뒤집는 것입니다.

Phase 3. 절반만 뒤집기

팰린드롬인지 확인하려면 숫자 전체를 뒤집을 필요가 없습니다. 앞쪽 절반과 뒤쪽 절반만 비교하면 됩니다.

예를 들어 1221을 봅시다.

left = 1221, right = 0

1 꺼냄 → left = 122, right = 1
2 꺼냄 → left = 12,  right = 12

이제 left == right입니다. 앞쪽 절반 12와 뒤집은 뒤쪽 절반 12가 같으므로 팰린드롬입니다.

홀수 자릿수인 12321은 이렇게 됩니다.

left = 12321, right = 0

1 꺼냄 → left = 1232, right = 1
2 꺼냄 → left = 123,  right = 12
3 꺼냄 → left = 12,   right = 123

중앙의 3은 비교에 필요 없습니다. 그래서 right / 10으로 가운데 자릿수를 제거한 뒤 left와 비교합니다.

코드는 이렇게 됩니다.

fun isPalindrome(x: Int): Boolean {
    if (x < 0) return false
    if (x != 0 && x % 10 == 0) return false

    var left = x
    var right = 0

    while (left > right) {
        right = right * 10 + left % 10
        left /= 10
    }

    return left == right || left == right / 10
}

왜 x % 10 == 0을 먼저 처리하나요?

0이 아닌데 마지막 자리가 0인 수는 팰린드롬이 될 수 없습니다.

• 10을 뒤집어 읽으면 01입니다
• 100을 뒤집어 읽으면 001입니다
• 120을 뒤집어 읽으면 021입니다

정수 표기에서 앞쪽의 0은 유지되지 않습니다. 따라서 마지막 자리가 0이라면, 앞쪽도 0이어야 팰린드롬이 될 수 있는데 그런 양의 정수는 0밖에 없습니다.

그래서 조건은 이렇게 씁니다.

if (x != 0 && x % 10 == 0) return false

0 자체는 팰린드롬이므로 제외하면 안 됩니다.

왜 while (left > right)에서 멈추나요?

right는 뒤쪽에서 꺼낸 자릿수를 뒤집어 만든 값입니다. 루프를 돌수록:

• left는 마지막 자리를 하나씩 잃습니다
• right는 자릿수를 하나씩 얻습니다

따라서 right가 left 이상이 되는 순간, 적어도 절반 이상을 처리한 것입니다.

짝수 자릿수에서는 두 값이 같은 길이에서 멈춥니다.

x = 1221
left = 12
right = 12

홀수 자릿수에서는 right가 가운데 자릿수 하나를 더 가진 상태로 멈춥니다.

x = 12321
left = 12
right = 123

그래서 마지막 비교는 두 가지를 모두 허용합니다.

return left == right || left == right / 10

• left == right: 짝수 자릿수 팰린드롬
• left == right / 10: 홀수 자릿수 팰린드롬에서 가운데 자릿수 제거

오버플로우는 왜 줄어드나요?

전체 숫자를 뒤집으면 2147483647 같은 입력에서 뒤집은 값이 Int 범위를 넘어갈 수 있습니다. 하지만 절반만 뒤집으면 right는 많아야 입력 자릿수의 절반 정도만 커집니다.

Int 최댓값은 10자리이고, 절반 뒤집기에서는 right가 대략 절반 근처의 자릿수에서 멈춥니다. 팰린드롬이 아닌 10자리 입력에서 한 번 더 진행되더라도 6자리 수준입니다. 그래서 right = right * 10 + left % 10이 Int 범위를 넘을 걱정이 사실상 사라집니다.

시간 복잡도는 O(d)입니다. 정확히는 절반만 처리하므로 반복 횟수는 d / 2에 가깝지만, 빅오 표기에서는 O(d)입니다. 숫자 크기 기준으로 쓰면 O(log10 x)입니다. 추가 공간은 O(1)입니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
121	true	앞에서 읽어도 뒤에서 읽어도 121
-121	false	음수 부호는 뒤집었을 때 끝으로 갈 수 없음
10	false	뒤에서 읽으면 01
0	true	한 자리 숫자는 팰린드롬
7	true	한 자리 숫자는 팰린드롬
1221	true	짝수 자릿수, 12 == 12
12321	true	홀수 자릿수, 가운데 3을 제외하면 12 == 12
12331	false	절반 비교가 맞지 않음

특히 10, 100, 120처럼 마지막 자리가 0인 양수를 놓치기 쉽습니다. 이 케이스를 먼저 걸러야 절반 뒤집기 비교가 단순해집니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
문자열 변환	O(d)	O(d)	가장 짧고 직관적이지만 follow-up 조건을 만족하지 않음
전체 숫자 뒤집기	O(d)	O(1)	문자열 없이 가능하지만 뒤집은 값의 오버플로우를 의식해야 함
절반 숫자 뒤집기	O(d) / O(log10 x)	O(1)	필요한 절반만 뒤집어 비교하는 최종 풀이

마무리

1. 음수는 팰린드롬이 아닙니다 — 부호가 숫자 뒤쪽으로 이동할 수 없기 때문입니다
2. 0이 아닌데 마지막 자리가 0인 수는 팰린드롬이 아닙니다 — 뒤집으면 앞쪽에 불필요한 0이 생깁니다
3. 전체 숫자를 뒤집을 필요는 없습니다 — 뒤쪽 절반만 뒤집어 앞쪽 절반과 비교하면 충분합니다
4. 홀수 자릿수는 가운데 숫자를 버리고 비교합니다 — left == right / 10 조건이 이 역할을 합니다
5. 절반 뒤집기는 문자열 없이 O(1) 공간으로 풀 수 있고, 전체 뒤집기보다 오버플로우 걱정도 작습니다 — 이 문제가 요구하는 핵심 풀이입니다