[Question] 4. 정수 n에 대하여 팰린드롬인지 알아내기

* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다.

먼저, 팰린드롬(palinedrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 똑같은 단어를 말한다.

정수 n에 대하여 팰린드롬인지 알아내는 방법을 구현하면 되고, 정수를 문자열로 변경해서는 안된다.

예제}

Input : 12345

Output : False

Input : -101

Output : False

Input : 11111

Output : True

Input : 12421

Output : True

일단 엣지 케이스를 살펴보자. 정수가 마이너스면 팰린드롬이 될 수 없다.

그리고 0이 아닌 정수가 0으로 끝난다면 이 경우 역시 팰린드롬이 될 수 없다.

주어진 숫자를 전반부와 후반부로 나눈다. 예를 들어 1233210이 주어지면, 123이 전반부이고 321이 후반부이다.

전반부(123)가 거꾸로 된 후반부(123)와 같다면 팰린드롬이다.

정수를 전반부와 거꾸로 된 후반부로 나누려면 while문을 써서 정수의 일의 자리수를 뽑아낸 후 정수를 10으로 나누면 정수의 각 숫자를 얻어낼 수 있다.

123321 -> 12332, 1 -> 1233, 2 -> 123, 3

이제 거꾸로 된 후반부는 10으로 곱한 뒤 뽑아낸 일의 자리 숫자를 더하면 된다.

0 + 1 -> 10 + 2 -> 120 + 3 = 123

이 방법을 거꾸로 된 후반부가 전반부보다 크거나 같을 때까지 반복하면 된다.

만약 주어진 숫자의 길이가 홀 수라면, 거꾸로 된 후반부에서의 1의 자리수를 없애주면 된다.

12321 - > 전반부(12), 거꾸로된 후반부(123)

전반부 = input

거꾸로된 후반부 = revertedHalf

bool IsPalindrome(int input) {
      if(input < 0 || (input % 10 == 0 && input != 0)) {
          return false;
      }

      int revertedHalf = 0;
      while(input > revertedHalf) {
          revertedHalf = revertedHalf * 10 + input % 10;
          input /= 10;
      }
      return input == revertedHalf || input == revertedHalf/10;
}

시간 복잡도 : O(log n)            // 숫자의 길이만큼 반복된다.

공간 복잡도 : O(1)