Palindrome Number

Algorithm
algorithm, leetcode

leetcode 문제링크

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

  • Input: 121
  • Output: true

Example 2:
Input: -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: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:
Coud you solve it without converting the integer to a string?

예?? 이걸 문자열화 하지 말고 풀라구요???

나의 풀이

난이도 easy만 먼저 풀어보는데 속도에 집착하다보니 난이도가 easy가 아닌 것만 같은 기분…

1
2
3
4
5
6
// 304ms 
var isPalindrome = function(x) {
  const str = x.toString();
  const reverseStr = str.split('').reverse().join('');
  return str === reverseStr
};

Hint: Beware of overflow when you reverse the integer.

네..그렇군요… 뒤집는 건 주의해야겠군요…세상에…
아래는 while문을 통해 앞 / 뒤로 접근해서 비교하도록 하는 방법인데,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 268ms
var isPalindrome = function(x) {
  const str = x.toString();
  const l = str.length - 1;
  let i = 0;
  let result = true;
  while(i <= l) {
    if(str[i] !== str[l - i]) {
      return (result = false);
    }
    i++;
  }
  return result;
}

반으로 나눠야 중복되는 비교를 안하겠구나 생각해서 아래와 같이 수정했지만 속도가 크게 개선되지는 않았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 260ms 속도 개선이 별로..
var isPalindrome = function(x) {
  const str = x.toString();
  const l = str.length;
  const half = Math.floor(l / 2);
  const strF = str.slice(0, half);
  const strB = str.slice(l % 2 === 0 ? half : half + 1);
  let i = 0;
  let result = true;
  while(i < half) {
    if(strF[i] !== strB[(half - 1) - i]) {
      return result = false;
    }
    i++;
  }
  return result;
};

혹시나 해서 reverse 메소드를 사용하는 방법을 반으로 나눠서 하는 방법으로 다시 풀어봤다.
300ms가 280ms로 속도가 개선되었으나 앞의 풀이 방법에 비하면 느리다.

1
2
3
4
5
6
7
8
9
10
11
12
// 280ms
var isPalindrome = function(x) {
  const str = x.toString();
  const l = str.length;
  if (l === 1) {
    return true;
  }
  const half = Math.floor(l / 2);
  const strF = str.slice(0, half);
  const strB = str.slice(l % 2 === 0 ? half : half + 1).split('').reverse().join('');
  return strF === strB
};

문자열화하지 않고 숫자인 상태에서 풀면 좀 더 빠를까해서 아래와 같이 풀었는데, 더 느려졌다. 아마 이 역시 주어진 수를 반으로 나눠서 푸는 게 아니라서 그런 것 같다.(수의 길이(?)만큼 비교하게 된다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 300ms 아악 더 느려졌다.
var isPalindrome = function(x) {
  if(x < 0) {
    return false
  }
  if(x < 10) {
    return true
  }
  let xClone = x;
  const arr = [];
  while(xClone) {
    const X = xClone % 10;
    xClone = parseInt(xClone / 10);
    arr.push(X % 10);
  }
  return x === parseInt(arr.join(''))
}

뭔가 숫자를 반으로 쪼갤 수 있으면 좋겠는데, 이 부분은 방법이 잘 생각나지 않아서 solution을 보기로 했다.
아래는 solution을 참고한 풀이

Approach 1: Revert half of the number

1
2
3
4
5
// C#
while(x > revertedNumber) {
    revertedNumber = revertedNumber * 10 + x % 10;
    x /= 10;
}

이부분을 통해 수를 반으로 나눠 반복문 안에서 비교할 수 있도록 하는 방법이다.
C#의 문법을 잘 모르지만 C#은 알아서 소수점 아래는 제거해주는 건지;; 아무튼 소수점 아래가 생겨버리므로 나는 JavaScript로 풀어야하니까 parseInt를 통해 정수로 계산되도록 했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 256ms
var isPalindrome = function(x) {
  let xC = x;
  if(x < 0 || (x % 10 === 0 && x !== 0)) {
    return false;
  } else if (x < 10) {
    return true;
  }
  let revert = 0;
  while(xC > revert) {
    revert = parseInt(revert * 10 + xC % 10);
    xC = parseInt(xC / 10);
  }
  return xC === revert || xC === parseInt(revert / 10);
}

Complexity Analysis

  • Time complexity : O(log10n)
    We divided the input by 10 for every iteration, so the time complexity is O(log10n)
  • Space complexity : O(1)

라는데, 복잡성 공부를 해야겠다… 댓글에서는 ‘왜 O(log10n)이냐 O(n)이 맞다’, ‘아니다 솔루션 저자가 맞다’로 의견이 분분한 듯한데 아직 잘 모르겠다;;

Share Comments