리트코드 - 9. Palindrome Number

리트코드 - 9. Palindrome Number

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

 

문제 설명

정수 x가 팰린드롬 인 경우 true를 반환하고, 그렇지 않은 경우 false를 반환합니다.

의사코드

if (x < 0)     false 리턴 copyX = x reversedX = 0 반복문 시작(copyX > 0 동안)     digit = copyX % 10     reversedX = reversedX * 10 + digit     copyX /= 10 반복문 종료 x == reversedX 리턴

 

풀이코드

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int copyX = x;
        int reversedX = 0;
        while (copyX > 0) {
            int digit = copyX % 10;
            reversedX = reversedX * 10 + digit;
            copyX /= 10;
        }

        return x == reversedX;    
    }
}

 

코드설명

문제의 요지는 역으로 해도 같은 수인가?를 물어보고 있다.

String으로 만든다면 투포인터를 이용해서 왼쪽과 오른쪽 포인터를 두고 가운데까지 확인하면 되겠지만,

문제의 추가 조건에서 String으로 만들지 않고 찾아볼수 있는지를 물어보고 있다.

 

따라서 x를 뒤집어서 같은지 비교해보면 된다.

먼저 x를 복사하여 copyX로 만들고 한자리씩 잘라 reversedX에 추가해주는데, 추가해줄 때마다 10씩 곱해 자리수를 추가해주어야 한다.

이렇게 해서 x와 reversedX를 비교하는 리턴문을 돌리면 완성이다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

투포인터에 꽂혀서 한 10분 생각해보다가 어짜피 수를 뒤집었을때 같으려면 가운데를 기준으로 양쪽이 같아야 함을 깨닳았다.

수학적인 기교(?)가 들어간 문제라 내심 재밌기도 했다.

 

다른 코드를 참고한 리팩토링

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }
        int reversedX = 0;
        while (x > reversedX) {
            int digit = x % 10;
            reversedX = reversedX * 10 + digit;
            x /= 10;
        }

        return x == reversedX || x == reversedX / 10;    
    }
}

투 포인터처럼 응용한 코드이다.

x를 복제하지 않고 직접 비교하는데 절반까지만 비교하는 방식이다.

 

x=12321 이라면, 처음 21까지만 확인하면 된다. 가운데 자리는 항상 같기 때문이다.

1221이어도 마찬가지다. 21만 확인하면 팰린드롬이 된다. 전부를 비교할 필요가 없는 것이다.

따라서 리턴에서 x == reversedX (x 자리수가 짝수일때)or x == reversedX / 10(x자리수가 홀수일때) 조건이 들어가는데,

이것때문에 10의 배수에서 문제가 된다.

 

예를 들어 20이라고하면 최종적으로 x=0이 되어있을 것이고 reverseX=2가 되는데 x == reversed /10 를 만족하기 때문이다.

 

그래서 처음 조건에서 10의 배수를 제외해주기 위해서 x % 10 == 0 을 추가하는데, 이것 때문에 x = 0 일때 또 문제가 된다.

0은 팰린드롬 숫자이기 때문인데, 0 % 10 = 0 이 false라서 잘못된 계산식이 된다.

 

따라서 조건을 하나 더 추가하면 완벽한 해결법(?)이 된다.

 

정리

팰린드롬 숫자를 확인하는 방법