[LeetCode] Palindrome Number 풀이

문제 링크

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

포인터 방식

• 시간복잡도 O(N)
  • N자리의 정수를 문자열로 변환하는 O(N)
  • N자리의 정수를 절반만 순회하기 때문에 O(N/2)
• 공간복잡도 O(N)
  • N자리의 정수를 문자열로 변환하는 O(N)

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        if (x < 10) return true;

        String target = x + "";
        int start = 0;
        int end = target.length() - 1;

        while (start < end) {
            char startCh = target.charAt(start);
            char endCh = target.charAt(end);
            if (startCh != endCh) {
                return false;
            }

            start++;
            end--;
        }

        return true;
    }
}

 

리버스 숫자 구하기

• 시간 복잡도 O(log(N))
  • 입력받은 정수를 N이라고 하고 그것의 자릿수를 D라고 했을 때, log(N) + 1
• 공간 복잡도 O(1)

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;

        if (x != 0 && x % 10 == 0) return false;

        int target = x;
        int reversed = 0;

        while (target > reversed) {
            reversed = reversed * 10 + target % 10;
            target/=10;
        }
        
        return target == reversed || target == reversed / 10;
    }
}