JS) leetcode - Add digits

Sal Jeong·2022년 9월 18일
0

최근 leetcode 문제를 풀면서 느낀 점이 있다. leetcode에서는 알고리즘을 submit하면 메모리 사용량과 런타임 시간을 알려주기 때문에, 이에 대해서 한 번 더 생각하게 된다.(물론 들쭉날쭉하게 표시되기 때문에 헷갈리고 실제로 의미없다는 이야기도 있지만, 나에게 적어도 퍼포먼스에 대해서 생각하는 계기를 주었다.)

1. Add Digits

https://leetcode.com/problems/add-digits/submissions/

문제 자체는 아주 간단한 것이었다.

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

 

Example 1:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.
Example 2:

Input: num = 0
Output: 0

받은 Int를 자릿수로 쪼개서 더하고, 1의 자리수가 될때까지 더하는 것이었는데

따라서

  1. 숫자를 스트링화한다
  2. split으로 array로 만든다.
  3. reduce로 arr 값을 더한다.
    3-1. 2. split array 길이가 1이라면, 그냥 그 값을 리턴한다.
    3-2. 2. aplit array 길이가 1 이상이라면 아직 더할 것이 남아있으니 한번 더 1.부터 iterate한다.

// first solution

var addDigits = function (num) {
  function numSplit(num) {
    return num.toString().split("");
  }
  function strReduce(arr) {
    return arr.reduce((acc, n) => acc + Number(n), 0);
  }

  function plusStr(num1) {
    const split = numSplit(num1);
    const sum = strReduce(split);
    if (split.length == 1) return sum;
    return plusStr(sum);
  }
  return plusStr(num);
};

첫번째 해결책은 이랬다.

2. 더 나은 방법은 뭘까?

아마, 내가 작성한 위 솔루션은 O(n)일 것이다.
toString O(n)
split O(n)
reduce O(n)
즉 3번의 for 문이 도는 형태가 되는 것이라고 생각하는데.

https://leetcode.com/problems/add-digits/discuss/579918/javascript-solutions-with-explanation

ps)위 url의 해설에 따르면 맞는 듯 하다.

몇 가지 생각해볼 만한 것은,

  1. String을 Array화 하지 않고 reduce하면 어떻지?
    사실 이것은 Python에서는 그냥 되는것인데, JS에서는 call해서 사용할 수 있을 것 같다. 거의 사용해본적은 없지만...
/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function (num) {
  function numSplit(num) {
    return (num+'');
  }
  function strReduce(arr) {
    return arr.reduce((acc, n) => acc + Number(n), 0);
  }

  function plusStr(num1) {
    const split = numSplit(num1);
    const sum = Array.prototype.reduce.call( // call 
    split,
    (acc, curr) => acc + Number(curr),
    0
    )
    if (split.length == 1) return sum;
    return plusStr(sum);
  }
  return plusStr(num);
};
  1. reduce를 그냥 for loop으로 대체하면 어떨까?
    JS의 각종 native 메소드들은 코드를 덜 적게 하는데 도움을 주지만, 실제로 퍼포먼스는 조금 느리다는 이야기를 들은 적이 있다.
/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function (num) {
  function numSplit(num) {
    return (num+'');
  }
  function strReduce(arr) {
    return arr.reduce((acc, n) => acc + Number(n), 0);
  }

  function plusStr(num1) {
    const split = numSplit(num1);
    let sum = 0;
    for(let i = 0; i<split.length; i++){
      sum += parseInt(split[i])
    }
    if (split.length == 1) return sum;
    return plusStr(sum);
  }
  return plusStr(num);
};

jsperf사이트가 접속이 되지 않는데,

https://jsben.ch/
에서 실제 체크를 해볼 수 있었다.

3. 실제 속도를 체킹해보니

위 사이트에서 나오는 값은 jsperf와 동일하게, ops/second 값으로 초당 몇번 실행되는지 확인하는 수치이다.

  1. Array.prototype.reduce.call을 사용했을 경우

call 메소드를 적용한 블록 2가 그냥 느리다. 사실 그럴거라고 생각은 하고 있었다.

  1. reduce를 for loop으로 변환했을 때,

reduce보다 for loop가 훨씬 좋은 것을 확인할 수 있었다.

사실 이 그래프의 내용을 알고 있었기 때문에, 어떻게든 예상된 결과라고 할 수 있을 것 같다.

다만 이렇다고 결코 reduce의 가치가 떨어진다고는 생각하지 않는데,

실제 코드를 작성하다 보면 for loop을 두세번씩 중첩하는 일도 있고,(물론 이것도 심사숙고하다보면 더 줄여나갈 수 있겠지만..) 그럴때마다 for loop을 여는 것은 가독성에 너무 큰 문제를 줄 수 있기 때문이다. 결국
reduce와 for loop을 놓고 생각했을 때, 결국 중요한 것은 속도 차이가 너무 크지 않다면 결국 가독성이 최고라는 것이라고 생각한다.

4. number 형을 효율적으로 string으로 바꾸는 법?

위 내용들을 찾으면서 검색하던 중,

다른 답안에서는 toString(str) 대신 '' + str을 사용해서 string화 한다는 것을 알게 되었다.

알고는 있는 내용이었지만, 이것이 속도가 더 빠를까?
(생각해보니, toString()보다 에러가 덜 나는 것은 기억이 나는데, 완전히 까먹고 있었다. 앞으로 이걸로 써야겠다.)

예를 들어,

(1928385).toString()
// 잘됨

null.toString()
// Uncaught TypeError: Number.prototype.toString requires that 'this' be a Number


null + '' = 'null'

undefined + '' = 'undefined'

// 이므로, 일단 빨간화면을 드러내지 않기 위해선 + ''를 쓰는 것이 나아 보인다.

https://stackoverflow.com/questions/14918778/why-concat-empty-character-is-faster-than-tostring

http://jsben.ch/ghQYR

의 내용에서 테스트 결과를 찾을 수 있었다.


var number = 27387329;
var str;

str = "" + number + ""; //1위
str = String(number); // 4위
str = number.toString(); //3위
str = "" + number; //2위

의 순서대로 빠른데, 1위인 "" + number + "" 가 가장 빠르고, 위처럼 빨간화면을 띄우는 일도 없으니 앞으로는 저렇게 사용하는 것이 나을 것 같다.

ps) 사파리에서는 측정 결과가 다르다.

반대로 toString()이 가장 빠르다는 것을 알 수 있었다.

그렇지만, toString()에서 역시 null object, undefined에서 에러가 나는 것은 똑같으니깐, 위의 string concat "" + nuber + ""을 사용하는 것이 가장 좋지 않은가 한다.

그런데 왜 이런 일이 일어나는 것일까?

https://stackoverflow.com/questions/14918778/why-concat-empty-character-is-faster-than-tostring

위 크롬 V8의 c function stacktrace에 따르면,
실제 toString()을 사용하는 경우 코드가 추가로 더 붙어있다고 하는데..

이 부분은 시간날 때 더욱 확인해보아야 할 것 같다.

profile
행복하기 위해 코딩합니다. JS 합니다.

0개의 댓글