코딩테스트 #4(팰린드롬Palindrome)

#4

정수(int)가 주어지면, 팰린드롬(palindrome)인지 알아내시오. 팰린드롬이란, 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말합니다. 단, 정수를 문자열로 바꾸면 안됩니다.

예제)

Input: 12345

Output: False

Input: -101

Output: False

Input: 11111

Output: True

Input: 12421

Output: True

코딩끄적끄적 게시판에 작성했던 팰린드롬 관련 알고리즘문제가 나왔다. 이 팰린드롬문제는 전에 포스팅했던 팰린드롬문제의 심화버전인 것 같다. 전 버전은 String(문자열)으로 되었기 때문에, 관련 메소드를 사용하여 손쉽게 풀었지만, 이번 문제는 int(정수)형 이기 때문에 관련 메소드를 사용할 수가 없다. (length 길이조차도... 사용할 수 없다..)

일단, 처음에 걸러낼 수 있는 것들을 생각해보자.

1) 숫자가 - (음수)인 경우

=> -10-1 이런 숫자는 존재하지 않는다. 만약에 숫자가 음수라면 팰린드롬이 될 수 없다.

2) 숫자 끝이 0으로 끝나는 경우

=> 0550 이란 숫자는 존재하지 않는다(0으로 시작하는 숫자는 존재하지 않으니까!). 만약에 숫자의 끝이 0으로 끝난다면 팰린드롬이 될 수 없다. 

이제 팰린드롬인지 아닌지 판단하는 로직을 생각해보자.

팰린드롬은 반으로 나눠, 앞부분과 뒷부분이 일치하는지 확인하여야 한다. 문자열이라면 index로 접근하여 for문을 돌려서 비교하면 되겠지만, 정수이기 때문에 나누기를 이용한다.

만약 1234321이라는 input이 있으면 10으로 나눠서(중간부분까지) 앞부분을 만들고, 뒷부분은 10으로 나눈 나머지에 10을 곱해가며(자리수 증가) 완성시킨다.  그 후 만들어진 앞부분과 뒷부분을 비교하면된다.

말로 설명이 힘드니(제가 설명을 못합니다.,) 코드를 보는게 더 편할듯 하다. 

   public static void main(String[] args) {
        /*
        Input: 12345
        Output: False

        Input: -101
        Output: False

        Input: 11111
        Output: True

        Input: 12421
        Output: True
        */
        
        System.out.println(solution(12345));
        System.out.println(solution(-101));
        System.out.println(solution(11111));
        System.out.println(solution(12421));
        System.out.println(solution(111111));
        System.out.println(solution(124421));
    }
    
    public static boolean solution(int input) {
        int revertedHalf = 0;
        if(input < 0 || (input%10 == 0 && input != 0))
            return false;
        
        while(input > revertedHalf) {
            revertedHalf = (input % 10) + (revertedHalf * 10);
            input = input/10;
        }
        System.out.println("revertedHalf : " + revertedHalf);
        System.out.println("input : " + input);
        
        return (input == revertedHalf) || (input == revertedHalf/10); 
    }