[LeetCode] 9. Palindrome Number (Python)

Problem

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

 

Solution

array

정수 x 가 주어지면 앞뒤 거꾸로 바꾸어도 동일한 숫자가되는지 체크하는 문제.

stack 을 사용하면되겠다고 생각했다.

 

몰랐는데 파이썬에서 string 을 거꾸로 뒤집는 방법이있었다 ㄷㄷ

아래가 바로 그 코드

s = str(x)
return s == s[::-1]

 

다른 방법은 10으로 나눈 나머지를 tmp 변수에 * 10 하며서 더해준다.

오리지널 x 는 10으로 나눈 몫으로 업데이트 해준다.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        
        rev = 0
        num = x
        while num > 0:
            rev = rev * 10 + num % 10
            num //= 10
        
        return x == rev

 

이렇게 풀어야 시간복잡도 O(N), 공간복잡도 O(1)로 더 효율적으로 풀 수 있다.

• 시간복잡도: O(N) (자릿수를 뒤집는 데 O(N))
• 공간복잡도: O(1) (추가 리스트나 문자열 저장 없이 숫자 연산만 사용)

Code

class Solution:
    def isPalindrome(self, x: int) -> bool:
        answer = True
        if x < 0:
            return False
        
        strX = str(x)
        st = []
        if len(strX)%2 == 0:
            for i in range(len(strX)):
                if i < len(strX)/2:
                    st.append(strX[i])
                else:
                    if st.pop() != strX[i]:
                        return False
        else:
            for i in range(len(strX)):
                if i < len(strX)//2:
                    st.append(strX[i])
                else:
                    if i == len(strX)//2:
                        continue
                    else:
                        if st.pop() != strX[i]:
                            return False
        return answer

 

Complexity

Time Complexity

stack에 문자열을 저장하므로 O(N)

 

Space Complexity

string 변수와 stack 에 문자열을 저장하므로 O(N)