leetcode - Reverse Integer

Algorithm
algorithm, leetcode

leetcode 문제링크

Given a 32-bit signed integer, reverse digits of an integer.

  • Example 1:
    • Input: 123
    • Output: 321
  • Example 2:
    • Input: -123
    • Output: -321
  • Example 3:
    • Input: 120
    • Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

나의 풀이

1
2
3
4
5
6
// Runtime: 80 ms
var reverse = function(x) {
    const range = 2 ** 31;
    const result = parseInt(x.toString().split('').reverse().join(''));
    return (result > (range - 1)) ? 0 : x >= 0 ? result : result * -1;
};

코드가 짧아보인다고 빠른게 아닌 것임을…
Big O Notation을 아직 제대로 이해하지 못했지만 제아무리 코드상 짧아보여도 반드시 좋은 코드인 것은 아니란 걸 알았다.(그리고 나의 코드가 그런듯…)

range = 2 ** 31은 Math.pow(2, 31)로 구해도 될 것 같고 숫자를 문자열 화하는 방법은 다양하다. ('' + x, ${x}, x.toString()…)

문제 자체가 풀기에는(정말 푼 것에만 의미를 두자면) 크게 어렵지 않았고, 나는 숫자를 reverse한다고 해서 당연히 1문자열로 만들어서, 2배열화해서, 3reverse메소드로 뒤집고 다시 4join메소드로 합쳐준 다음 5숫자화하면 되는 것 아닌가?라고 생각했다.
그리고 이게 거의 공식처럼 머릿속에 있었는데, 다른 사람들 풀이를 보니까 생각이 넓어지는 기분이다.

다른 사람 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 64ms
var reverse = function(x) {
  var isNeg = x < 0;
  var result = 0;
  
  x = Math.abs(x);
  
  while(x) {
      var lastDigit = x % 10; // 33 % 10 = 3
      result *= 10; // 0
      result += lastDigit; // 3
      x = parseInt(x / 10); // 3
  }

  result = isNeg ? -result : result;
  
  if(result > Math.pow(2, 31) - 1 || result < -Math.pow(2, 31)) {
    return 0;
  }
  
  return result;
};

이 풀이는

  1. 먼저 음수인지 여부를 저장해둔다.
  2. x를 Math.abs()를 통해 절대값으로 만든다.
  3. 만약 그 전에 result에 저장된 값이 있으면 10을 곱해줘서 자리수를 올린다.
  4. x를 10으로 나눈 나머지를 result에 더해준다.
  5. x에는 다시 10으로 나눈 정수값만 저장하면서 x가 0이 될때까지 반복한다.
  6. 이렇게 reverse한 수가 음수인지 여부에 따라 다시 음수화시켜주고
  7. 만약 제한범위를 넘어서면([−231, 231 − 1]) 0을 반환하고 아니면 result를 그대로 반환한다.

위의 풀이와 비슷한데 조금 다른 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 68ms
var reverse = function(x) {
  var MAX = Math.pow(2, 31) - 1;
  var number = 0, 
      symbol = 1;

  if(x < 0){
    x = Math.abs(x);
    symbol = -1;
  }

  while(x > 0){
    number = number * 10 + x % 10;
    x = Math.floor(x / 10);
  }

  return number > MAX ? 0 : symbol * number;
};

1
2
3
4
5
6
7
8
9
10
11
// 76ms
const reverse = function(x) {
    if (x==0) return 0
    let isPositive = x > 0
    
    let digits = (isPositive)? x.toString().split("").reverse()
                    : (-x).toString().split("").reverse()
    let num = parseInt(digits.join(''), 10)
    if (num >= 2147483647) return 0
    return num * (isPositive? 1: -1)
};

이 풀이는 나의 경우 Math.pow(2, 31)내지는 2 ** 31로 구하도록 했는데 이미 구해진 값을 넣어서 연산을 하나 줄였다.

대체로 while문을 통해서 10을 이용한 연산을 통해 자리수를 바꿔주는 방법이 문자열 → 배열 → reverse로 하는 방법보다 빠른 것 같다.

Share Comments