리트코드 - Palindrome Number

https://leetcode.com/problems/palindrome-number/description/

Palindrome Number - LeetCode

 

해당 숫자가 팰린드롬인지 여부를 확인하는 문제이다. 즉 앞뒤가 똑같아야 한다는 의미. 따라서 가장 간단한 풀이는 문자열로 바꿔서 역순으로 바꾼다음에 바꾼지 비교하기만 하면 풀 수 있다.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        x = str(x)
        x_reverse = x[::-1]
        return x == x_reverse

1. 시간 복잡도: O(n)
   • str(x): 정수를 문자열로 변환하는 데 O(n) 시간이 소요된다. 여기서 n은 숫자의 자릿수입니다.
   • x[::-1]: 문자열을 뒤집는 데 O(n) 시간이 소요된다.
   • x == x_reverse: 두 문자열을 비교하는 데 최대 O(n) 시간이 소요된다.
   • 따라서, 전체 시간 복잡도는 O(n).
2. 공간 복잡도: O(n)
   • 변환된 문자열 x와 뒤집힌 문자열 x_reverse를 저장하기 위해 O(n)의 추가 공간이 필요하다.

개선된 풀이

문제의 "Follow up" 부분에 따르면 정수를 문자열로 변환하지 않고 문제를 해결할 것을 제시한다. 이를 위한 한 가지 방법은 정수를 숫자 단위로 분해하고, 이를 통해 팰린드롬을 확인하는 것이다.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False

        reverted_number = 0
        while x > reverted_number:
            reverted_number = reverted_number * 10 + x % 10
            x //= 10

        return x == reverted_number or x == reverted_number // 10

숫자를 반으로 나누고, 뒤집힌 숫자(reverted_number)가 원래 숫자(x)와 같거나, 홀수 길이 숫자의 경우 가운데 숫자를 제외하고 같은지 확인하는 방법이다.

1. 시간 복잡도: O(n/2)
   • 숫자를 분해하고 반만큼만 비교하기 때문에 시간 복잡도가 O(n/2)이다.
2. 공간 복잡도: O(1)
   • 추가적인 공간을 사용하지 않고, 주어진 숫자만으로 계산을 수행하기 때문에 공간 복잡도는 O(1)이다.