[Python/LeetCode]Palindrome Number

오늘 오랜만에 아메리카노를 마셨더니 잠이 안들어서 어쩔 수 없이 일어났다. 알고리즘을 풀면 졸려질까 싶은 생각에 리트 코드를 열었는데, 오히려 더 쌩쌩해졌다.

 

1. 문제

Given an integer x, return true if x is palindrome integer.
An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

 

팰린드롬 수는 101, 121, 1221과 같이 뒤집어도 같은 수다. 처음에 문제를 보자마자 str로 변환하고, 뒤집은 값과 비교하면 되겠다고 생각했다. 

 

그런데 문제의 예제를 끝까지 읽다보니 Follow up에

Follow up: Could you solve it without converting the integer to a string?

str로 변환하지 않고 풀 수 있냐고 해서 리스트로 풀었는데 더 느리다. 똑같은 로직으로 풀어도 C++을 사용하면 속도, 메모리 효율성이 90을 넘는데, 파이썬으로 리스트로 풀면 속도, 메모리 둘 다 40대로 떨어진다. 

 

2. 코드

[1] string으로 변환해서 푼 코드

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

Runtime: 56 ms, faster than 79.53% of Python3 online submissions for Palindrome Number.

Memory Usage: 14 MB, less than 98.58% of Python3 online submissions for Palindrome Number.

 

메모리는 적게 사용하지만, 속도는 느리다.

 

[2] 리스트를 사용해서 푼 코드 

 

x가 0인 경우 무조건 True고 음수인 경우 무조건 False이니, 이 두가지는 제일 먼저 처리한다.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x == 0:
            return True
        if x < 0:
            return False
        
        num = []
        while x!=0:
            x, y = x//10, x%10
            num.append(y)
            
        return num == num[::-1]

Runtime: 76 ms, faster than 25.50% of Python3 online submissions for Palindrome Number.

Memory Usage: 14.1 MB, less than 75.67% of Python3 online submissions for Palindrome Number.

 

리스트가 처참한 성적을 거뒀다. 그래서 divmod를 사용해봤다.

왜냐면 divmod는 큰 숫자를 다룰 때 빠르고 작은 숫자를 다룰 때는 직접 x//10, x%10을 하는 것이 빠르기 때문이다.

 

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x == 0:
            return True
        if x < 0:
            return False
        
        num = []
        while x!=0:
            x, y = divmod(x, 10)
            num.append(y)
            
        return num == num[::-1]

Runtime: 84 ms, faster than 17.19% of Python3 online submissions for Palindrome Number.

Memory Usage: 14.3 MB, less than 13.91% of Python3 online submissions for Palindrome Number.

 

결과는 더 처참했다. 아무래도 0이 될 때 까지 계속 나누니까 느릴거라고 생각하긴 했는데 정말 엄청난 결과가 나왔다.