[알고리즘] Palindrome Number

문제 정보

출처 : leetcode
난이도 : easy

[문제]
Given an integer x, return true if x is a palindrome, and false otherwise.

[예제]
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left

내풀이

앞뒤가 같은 수를 구해야해서 char[]에 넣어서 for문을 x.length의 1/2만큼 돌리면서 앞뒤를 비교하는 코드를 구현했다.
-131을 뒤집으면 131-가 되기 때문에 음수는 무조건 false를 return하도록 하였다.

시간복잡도 : O(n)
공간복잡도 : O(n)

class Solution {
    public boolean isPalindrome(int x) {
        char[] charX = Integer.toString(x).toCharArray();

        if (x < 0) {
            return false;
        }
        for (int i = 0; i < charX.length/2; i++) {
            if (charX[i] != charX[charX.length - i -1]) {
                return false;
            }
        }

        return true;
    }
} 

runtime : 6 ms
memory : 43.1 MB

개선하기

1. 일단 무조건 false를 return하는 경우를 추가하였다.
   • x가 음수인 경우
   • x가 0이 아니면서 10으로 나눴을때 나머지가 0인 경우
2. 10으로 나눠가며 숫자를 뒤집으면 공간복잡도를 줄일 수 있다. 숫자를 반만 뒤집어서 revertNum을 만든다.

시간복잡도 : O(logN)
공간복잡도 : O(1)

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }

        int revertNum = 0;
        while(x > revertNum) {
            revertNum = revertNum * 10 + x % 10;
            x /= 10;
        }

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

runtime : 4 ms
memory : 42.9 MB

개선한대로 실행하면 시간복잡도뿐만 아니라 공간복잡도까지 줄어든다.