[Leetcode] 9. Palindrome Number

1. 문제

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.


Constraints:

-231 <= x <= 231 - 1


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

---

2. 배운점

 

몫 구하기

floor 까먹고 있었는데 다시 기억났다. 사실 floor를 사용할 필요없이 // 문법을 사용하여 몫만 구하면 된다.

x = x//10

 

숫자 거꾸로 구하기

newNum = newNum * 10 + x%10

---

3. 내 풀이

 

str으로 바꾸는게 일반적이다.

 

class Solution:
	def isPalindrome(self, x: int) -> bool:
		x = str(x)
		if x[0] == '-':
			return False
		for ch in x:
			if len(x) == 1:
				return True
			elif ch == x[-1] and len(x) > 2:
				x = x[1:-1]
			elif ch == x[-1]:
				return True
			else:
				return False

 

 

integer로 풀었다.

from math import floor


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

		nums = []
		while x > 0:
			q = x % 10
			nums.append(q)
			x = floor(x / 10)

		for num in nums:
			if len(nums) == 1:
				return True
			elif num == nums[-1] and len(nums) > 2:
				nums = nums[1:-1]
			elif num == nums[-1]:
				return True
			else:
				return False

 

 

 

4. 해법

 

내 방식은 너무 느리고 메모리도 많이 사용했다. 다른 사람들의 해법은 아래와 같다.

 

 

str 방법

0보다 작은지만 체크하고 [::-1] 문법을 이용하여 str을 reverse 했을 때도 같은지만 본다

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

 

int 방법

 

이 방법은 숫자를 뒤에서부터 거꾸로 저장하는 방식이다. 나머지를 구한 뒤 newNum에 넣어주는데, 이전 newNum에 있던 부분에 10을 곱해서 자릿수를 올린 뒤 나머지를 더해주는 방식이다. 예를 들면 아래와 같다.

 

Example, if x = 15951, then let's create reverse of x in loop. Initially, x = 15951, revX = 0

x = 1595, revX = 1

x = 159, revX = 15

x = 15, revX = 159

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

 

더 빠른 방법

첫 if문에서 맨 마지막 자릿수가 0이면 맨 앞자리 수가 0일 수가 없다는 사실을 바탕으로 False처리를 해줬다.

 

Palindrome이라 절반만 보면 된다. 그래서 x는 한 자리씩 깎아내면서 거꾸로 올라가는 result값이 x > result 일때까지만 while문이 적용됐다. 

def isPalindrome(self, x: int) -> bool:
	if x < 0 or (x > 0 and x%10 == 0):   # if x is negative, return False. if x is positive and last digit is 0, that also cannot form a palindrome, return False.
		return False
	
	result = 0
	while x > result:
		result = result * 10 + x % 10
		x = x // 10
		
	return True if (x == result or x == result // 10) else False

 

 

---

 

참조

 

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