[LeetCode/Python] 9. Palindrome Number

문제 링크: https://leetcode.com/problems/palindrome-number/?envType=study-plan-v2&envId=top-interview-150

 

숫자를 문자열로 바꿔서 풀면 아주 쉬운 문제다.

근데 문제 말미에 문자열로 안바꾸고 풀어보라는 챌린지가 있길래 시도했다가 처참히 실패했다..ㅠ

 

일단 인풋을 문자열로 바꾸지 않고 숫자 자체로 두고 푼 코드는 아래와 같다.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 9:
            return False
        
        while x > 0:
            n = len(str(x))
            divisor = 10 **(n-1)

            left = x // divisor
            right = x % 10
            
            if left != right:
                return False
            
            x = (x % divisor) // 10
        
        if x == 0:
            return True
        else:
            return False

 

케이스는 대부분 통과하지만, 100021 처럼 중간에 0이 들어간 케이스는 제대로 판별이 어렵다.

왜냐하면 숫자로만 대칭을 판단하기 위해 x를 업데이트해주는데 이 때, 0이 앞자리에 있을 경우는 숫자 처리를 하면서 0이 사라지기 때문이다 ㅠㅠ

뭔가 0이 중간에 들어갔을 때 숫자를 유지하면서 예외처리를 해줄 방법이 아무리 생각해도 떠오르지 않아서 그냥 포기하고 문자열로 문제를 풀었다..

 

[내 풀이]

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

문자열로 바꾸면 쏘 이지....ㅎㅎ

파이썬은 진짜 문자열 문제 푸는데는 탑 언어다...

 

 

[다른 풀이]

숫자로만 푼 천재 사람들의 풀이....

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x<0:
            return False

        inputNum = x
        newNum = 0
        while x>0:
            newNum = newNum * 10 + x%10
            x = x//10
        return newNum == inputNum

 

x의 palindrome 숫자를 newNum으로 직접 만드는 것이다. 이렇게 되면 0이 들어가 있든 없은 palindrome 여부를 판단할 수 있다!

 

x의 일의 자리 숫자들을 newNum으로 넣어주고, 해당 숫자를 이제 x에서 제외시킨다. (몫만 남긴다)

그렇게 된다면 원래 x의 10의 자리 숫자가 그 다음 일의 자리 숫자가 된다.

원래 newNum에 있었던 숫자는 다음 자릿수로 올라가야하므로 10을 곱하는 것이다.

 

이 반복문은 x의 숫자가 없어질 때까지, 즉 x가 0이 될 때까지 반복한다.

 

시간 복잡도

n은 x를 문자열로 바꾸었을 때 길이

=> O(n)

 

 

list[::-1]는 리스트나 문자열을 새롭게 생성하여 각 원소를 뒤집은 순서로 복사한다.

리스트의 각 요소를 새 리스트에 복사해야 하므로 리스트의 길이만큼 연산이 필요! 따라서 시간 복잡도는 O(n)