[알고리즘/자바스크립트] 재귀를 이용한 배열 요소 개수 구하기 (Array Deep Count)

-해당 문제는 codewars사이트의 level6 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

 

[문제] Array.prototype.length will give you the number of top-level elements in an array. Your task is to create a function deepCount that returns the number of ALL elements within an array, including any within inner-level arrays.

deepCount([1, 2, 3]);  
//>>>>> 3
deepCount(["x", "y", ["z"]]);  
//>>>>> 4
deepCount([1, 2, [3, 4, [5]]]);  
//>>>>> 7

The input will always be an array.

---

[문제 해석] Array.prototype.length는 배열의 가장 상위 레벨 요소의 개수를 알려줄 것이다. 너의 임무는 배열 내부의 모든 요소들의 개수를 구하는 것이다. 예를 들어서 [1, 2, [3, 4, [5]]]가 주어진다면 1차적으로 배열의 요소의 개수는 1, 2, [] 이렇게 3개가 된다. 그리고 2차적으로 [3, 4, [5]]에서 요소의 개수는 3, 4, [] 이렇게 3개가 된다. 마지막으로 [5]에서 요소의 개수는 1개이므로 3 + 3 + 1 = 7을 return해야 한다. 함수의 파라미터는 항상 배열이 될 것이다.

 

 

---

 

 

재귀 함수는 개념적으로 이해하기는 매우 쉬운데 막상 사용하려고 하면 생각보다 매우 어렵다.

자칫하면 무한루프에 빠지기 때문에 Base case도 잘 생각해서 써줘야하고

재귀를 사용했을 때 함수 호출이 어떤 식으로 돌아가는지 머리 속에 잘 안그려지는 것 같다.

 

위 문제도 비교적 간단한 문제였지만 문제를 해결하는 데 시간이 꽤 오래걸렸다.

 

function deepCount (arr) {
  if (arr.length === 0) {
    return 0;
  }

  let sum = 0;
  function count (arr) {
    sum += arr.length;
    for (var i = 0; i < arr.length; i++) {
      if (typeof arr[i] === 'object') {
        count(arr[i])
      }
    }
    return sum;
  }
  return count(arr);
}

 

최초로 짠 코드이다. deepCount() 함수 안에

count() 함수를 다시 선언하여 재귀 호출하였다. 

 

위 코드로도 답은 나오긴 하지만

분명히 함수 안에 함수를 선언하지 않고 하는 방법이 있을게 분명해서 다시 고민해보았다.

 

그리고 어떤 요소가 배열인지 아닌지 판별하기 위해서

typeof를 사용하였는 데, typeof는 배열뿐만 아니라

객체도 'object'라고 판별하고 null도 'object'라고 판별하므로 매우 부적합한 방법이었다.

배열인지 판별하고 싶을 때는 Array.isArray() 메소드를 사용해야 한다.

 

 

 

function deepCount (arr) {
  let sum = arr.length;
  for (var i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      sum += deepCount(arr[i]);
    }
  }
  return sum;
}

 

그리고 꽤 오랜 시간에 걸쳐 다시 정리한 코드이다.

이 코드의 실행 과정을 정리해보면 아래와 같다.