[LeetCode - Easy] 9. Palindrome Number

해석과 풀이는 개인적인 부분이기 때문에 참고만 하시길 바랍니다. 다른 접근 및 풀이는 언제나 환영합니다. 댓글로 남겨주세요.

 

1. 문제

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

* palindrome [pælɪndroʊm]: 회문(回文: madam이나 nurses run처럼 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어나 구)

 

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.

 

2. 해석

숫자가 주어질 때 앞으로 읽어도, 뒤로 읽어도 동일한 숫자일 경우 true, 아닐 경우 false를 반환한다.

 

3. 풀이

- 필자는 아래와 같이 접근했다.

 ① 숫자를 문자로 convert 한 뒤에 ( Integer.toString() )

 ② 문자를 char타입 배열로 담아서 ( toCharArray() )

 ③ 하나씩 꺼내면서 꺼꾸로 조합한 문자를 만들어  ( for문, += 연산자 사용)

 ④ 기존 문자와 새로 조합한 문자가 동일한지 비교 ( 문자열비교 - equals() )

class Solution {
    public boolean isPalindrome(int x) {

        String input = Integer.toString(x);
        char[] str = input.toCharArray();

        String revInput = "";
        for(int i = str.length - 1; i >= 0; i--){
            revInput += str[i];
        }

        if(input.equals(revInput)){
            return true;
        }else {
            return false;
        }
    }
}

 

4. 고수들(?)의 접근 및 풀이 (leetCode)

- 당연 음수인 경우는 묻지도 따지지도 말고 제외시켜야하고 10으로 나눠서 딱 떨어지는 경우도 제외시켜야 한다.

- Could you solve it without converting the integer to a string? 이런 질문에 대해 고수들은 수학적 이해를 바탕으로 접근을 한 듯 보인다. (결국 수학을 잘 해야한다. ㅠㅠ)

 

예) 125를 palindrome 숫자인지 알아볼 경우, 125를 10으로 나눌 때 나머지는 순서대로 5, 2, 1 이 나온다.

그 나머지에 10을 곱해서 다시 나머지를 더하면 reversed 숫자가 나온다.

 

digit => 125 % 10 = 5 (나머지)

reversed => 0 * 10 + 5 = 5 ( 처음 reversed는 0, reversed 된 수에 10을 곱해 나머지를 더함)

temp = 125 / 10 = 12 (몫)

 

digit => 12 (temp) % 10 = 2 (몫을 계속 10으로 나눈 나머지)

reversed => 5 * 10 + 2 = 52 ( 위에 reversed 된 수에 10을 곱하고 나머지를 더함)

temp = 12 / 10 = 1 (몫)

 

digit => 1 (temp) % 10 = 1

reversed => 52 * 10 + 1 = 521

temp = 1/ 10 = 0 ( 더이상 몫이 없을 때 까지)

 

결국 10으로 나눴다가 나머지를 빼두고 다시 10으로 곱하면서 나머지를 뒤에 붙이는 식이다.

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

        long reversed = 0;
        long temp = x;

        while (temp != 0) {
            int digit = (int) (temp % 10);
            //System.out.println("digit => " + temp + " % 10 = "+ digit);
            
            //System.out.print("reversed => " + reversed + " * 10 + " + digit + " = ");
            reversed = reversed * 10 + digit;
            
            //System.out.println(reversed);
            
            temp /= 10;
            
            //System.out.println("temp = " + temp);
            //System.out.println("");
        }

        return (reversed == x);
    }
}

121을 넣었을 경우 reversed 숫자 또한 동일함을 알 수 있다.

 

digit => 121 % 10 = 1

reversed => 0 * 10 + 1 = 1

temp = 12

 

digit => 12 % 10 = 2

reversed => 1 * 10 + 2 = 12

temp = 1

 

digit => 1 % 10 = 1

reversed => 12 * 10 + 1 = 121

temp = 0