09 Palindrome Number

1. Description

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 a palindrome while 123 is not.

2. Algorithms

iteration	i	str_num[i]	back_num
1	0	'1'	'1'
2	1	'2'	'12'
3	2	'1'	'121'

class Solution:
    def isPalindrome(self, x: int) -> bool:
        back_num = ''
        str_num = str(x)
        
        for i in range(len(str_num)-1, -1, -1) : 
            back_num += str_num[i]
            
        if back_num == str_num : 
            return True 
        return False
        
class Solution:
    def isPalindrome(self, x: int) -> bool:
		return str(x) == str(x)[::-1]

1. 반전된 수를 저장할 back_num과 x의 숫자를 하나씩 추출할 str_num 생성
2. 인덱스가 감소하는 for loop를 통해 back_num에 값을 저장
3. if 문을 통해 str_num과 back_num 비교

iteration	while	x	revertedNumber
1	True	12	1
2	True	1	12
x	revertedNumber // 10
1	1

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

1. 음수와 0을 제외한 10의 배수는 palidrome number가 될 수 없으므로 제외함
2. 전체 데이터를 확인할 필요 없이 절반의 인덱스의 값이 서로 같은지 확인하기 위해 뒤에서부터 숫자를 추출해 저장할revertedNumber를 설정
3. while문을 통해 x는 10의 뒷자리부터 제거하고, revertedNumber은 10의 뒷자리부터 업데이트함
4. 짝수 인덱스의 경우에 x와 revertedNumber은 같게 되지만, 홀수 인덱스의 경우 revertedNumber이 중앙값을 마지막에 저장하게 되므로 10을 나눈 몫과 비교함

이런 코드는 도대체 어떻게 생각하는거지? 사실 절반의 인덱스로 나누면 TimeComplex가 좀 더 줄어들지 않을 까 했는데, 몫과 나머지로 숫자를 업데이트 할 생각은 못하고 있었다.

 

숫자조작 알고리즘 -> str()을 쓰지 않고 몫과 나머지로 접근해볼것

3. Conclusion

• Code 1's Time Complexity : $O(N)$
• Code 2's Time Compexity : $O(log_{10}(N))$