Flatten 함수 🔫

사건

이번 주 과제 중 하나였던 flatten 함수 구현하기다.

_.flatten(array)

복잡함 없이 해당 함수는 배열을 첫 번째 매개변수로 받는 간단한 함수다. 기능 구현 과정은 안그랬지만.
해당 함수의 설명 또한 간단하다.
아무리 array의 중첩배열의 깊이가 깊어도 single level로 평탄화 시켜주는 기능을 갖고 있는 함수다.

하나의 레벨만을 평탄화 시키는 기능 조차 구현이 힘들겠다 생각했지만,
얼마나 깊든 모든 중첩 배열을 평탄화 시킨다는 것은 막막했다.

의사코드

위 기능 구현을 시작하기에 앞서 의사 코드부터 작성해봤다

1. 주어진 배열 그 자체를 건드리기 보다는 새로운 배열을 만든다.
2. 반복문으로 배열 내 첫 번째 인덱스부터 끝까지 순회한다.
3. 순회하는 중 조건문을 이용하여 해당 인덱스가 배열인지 아닌지 확인한다.
4. 배열이 아니라면 단순히 해당 값을 새 배열에 넣어준다.
5. 배열이라면 해당 배열 내의 값에만 접근하여 새 배열에 넣어준다.

이렇게 총 5단계의 의사코드로 구현한 기능은 하나의 레벨만을 평탄화 시켜주는 것이었다.

위의 간단한 기능부터 구현하기로 했다.
이를 위해서는 위 의사코드를 조금 더 코드적으로 구체화 할 필요가 있었다.

1. 새 배열을 변수로 선언해 할당하기, let result = [ ]
2. 배열의 길이 구하기, for문을 이용하여 배열 길이까지만 반복하기
3. if문에 의해 n번째 인덱스의 값이 배열이 아니라면 result에 push()하기
4. n번째 값이 배열이라면 result와 n번째 인덱스의 배열과 concat()으로 합쳐 하나의 배열 만들기

위 의사코드를 코드로 구현해보자.
여러 고민과 우여곡절이 있었지만 구현에 첫 성공했던 코드는 이렇다.

function flatten(array) {
  let result = [];
  
  for (let i = 0; i < array.length; i++) {
    if (Array.isArray(array[i]) === false) {
      result.push(array[i]);
    }
    else if (Array.isArray(array[i])) {
      result = result.concat(array[i]);
    }
  }
  return result;
}

위를 아래 배열로 실행하게 되면,

const nestedArray = [
      1,
      [2],
      [3, [[[4]]]],
      [[5], [6], [7, 8, 9, [10], [[11]], 12, 13, [14], 15]],
    ];

// 결과값
[1, 2, 3, [[[4]]], [5], [6], [7, 8, 9, [10], [[11]], 12, 13, [14], 15]]

위 처럼 한층의 중첩배열이 평탄화된 배열이 된 것을 확인할 수 있었다.

분석

위 코드를 베이스로 본래 기능을 구현할 수 있을까?
배열 깊이의 범위가 정해져 있지 않고 예제별로 다 다를텐데 어떻게 범위를 정해야할까?
해답은 될 때까지만 반복하기다.
말이 쉽지, 위 방법을 사용하려면 어떻게 해야 될까?
진짜 해답은 리서치 과제 목록에 있었다.
그것은 재귀함수였다.

재귀 함수 구현 시 주의사항, 실행 흐름

재귀함수의 원리는 이러했다.

function recursive(num) {
  if (num <= 0) {
    return console.log('탈출 조건에 걸려 재귀함수 종료.');
  }
  console.log(num);
  num--;
  recursive(num);
}
recursive(5);

기본 구조는 함수 내에서 본인을 호출하되 의도한 바가 완료되면 종료되게끔 조건문을 거는 것이었다.

발전

위 재귀함수를 내 의사코드에 적용시키면 어떨까?
먼저 의사코드를 써보자.
뼈대는 기존의 배열 한 층 평탄화 코드와 같았다.

1. 새 배열 result 만들기
2. 배열의 길이까지 반복문으로 순회하기
3. 만약 배열이 아니라면 push()로 result에 단순 추가하기
4. 배열이라면 해당 배열과 result 와 concat()으로 합치기
5. 배열 길이까지 도달하여 반복문이 멈추면 한층 평탄화된 result 배열 완성
6. result 배열을 반복문으로 순회하기
7. 배열 내 배열이 있다면 result 배열을 flatten 함수에 넣어 재귀호출 하기

여러 실수와 에러들을 걸쳐 얻어낸 결과는 이거였다.

_.flatten = function unpack(nestedArray) {
  let result = [];
  for (let i = 0; i < nestedArray.length; i++) {
    if (Array.isArray(nestedArray[i]) === false) {
      result.push(nestedArray[i]);
    }
    else if (Array.isArray(nestedArray[i])) {
      result = result.concat(nestedArray[i]);
    }
  }
  for (let j in result) {
    if (Array.isArray(result[j]))
    unpack(result);
  }
    return result;
};

위 코드로써 완벽히 flatten의 기능을 구현했..
으면 좋았겠지만 당연하게도 실행 결과는 의도했던 결과에 조금 빗나간 정도도 아니었다.

문제 직면

결과는 이러했다.

우측의 result에서 보이는 바와 같이 순차적으로 반복문에 의해 반복되며 재귀함수로 배열이 있으면 result 와 그 배열을 다시금 합쳐주며 평탄화를 진행되었다.
그리고 마침내 모든 중첩배열이 사라진 형태로 단일 레벨의 배열이 result 이 담기는 것을 확인했다.
그렇게 result는 반환문을 만나 결과를 반환하기만 하면 됐는데 코드가 잘못된건지 result 배열은 다시 여러 중첩배열을 가진 채 코드를 반복하기 시작했다..
그렇게 엉망진창으로 코드가 반복되다가 여러 중첩배열을 가진 채로 결과가 나왔다.

질문

질문의 내용은 간단했다.
해당 코드로 디버깅을 수차례 진행하며 문제가 되는 포인트를 찾아 나섰지만
명확하게 어디서부터 잘못 되었는가를 찾을 수 없었던 나는 해당 코드를 멘토 분께
실시간으로 시연하며 어디서부터 어떻게 잘못됐는지를 여쭤보았다.
멘토 분의 답은 이러했다.

_.flatten = function unpack(nestedArray) {
  let result = [];
  for (let i = 0; i < nestedArray.length; i++) {
    if (Array.isArray(nestedArray[i]) === false) {
      result.push(nestedArray[i]);
    }
    else if (Array.isArray(nestedArray[i])) {
      result = result.concat(nestedArray[i]);
    }
  }
  for (let j in result) {
    if (Array.isArray(result[j]))
    unpack(result);
  }
    return result;
};

위 하이라이트 된 영역 위의 반복문을 마치고 한번의 평탄화를 거친 배열을 하이라이트 된 코드를 만나면서
문제가 발생했다. 과정은 이렇다.

1. 한층 평탄화된 배열을 반복문으로 돈다.
2. j번 째의 값으로 배열을 만날 때까지 진행한다.
3. 배열을 만나게 되면 재귀한다.
4. 반복문은 j번째까지 진행하고 일시 정지된다.
5. 재귀를 진행하고 한층 더 평탄화된 배열을 만든다.
6. 해당 배열로 밑의 하이라이트 반복문을 만나 0번째부터 다시 배열인가 아닌가를 확인한다.
7. 또 다른 j 번째에서 배열을 만난다.
8. 위 3 - 7번이 반복된다.

이렇게 위 과정을 거치면서 매번 반복문을 만날 때마다 일시 정지가 되어 마저 진행되지 않았던 반복문이 한번 완전히 평탄화를 거치고 나서야 다시 진행되는 것이었다.
이는 콜스택에서 진행되다가 다른 호출문을 만나 호출문의 실행 컨텍스트 쌓이고 또 쌓이며 FILO가 되었던 것이다.

멘토 분께선 재귀함수의 이해도를 조금 더 높히는게 해당 코드의 구현에 도움이 될거라고 하셨다.
아래가 재귀함수에 대한 링크

재귀함수 3단계 작성법

피드백 정리

재귀함수를 공부하고 나서
먼저 든 생각은 위 하이라이트 된 코드를 고치는 것보다는 해당 코드에서 문제가 발생하니 삭제하는 것이었다.
해당 코드를 삭제하려면 대신에 어떤 코드를 써야될까?
답은 정말 간단했다.
조건문 내에 재귀함수를 넣는 것이었다.
그 외에 수정사항으로는 먼저
반복문으로 인덱스에 접근하는 방식보다 그 자체의 순서를 순회하기 위해 for…of 를 쓰기로 했다.
그리고 헷갈림을 방지하기 위해 반복문일 때의 조건을 if문에 넣기로 했다.
그리고 반대의 조건은 간단하게 else만을 사용했다.

_.flatten = function unpack(nestedArray) {
  let result = [];
  
  for (let item of nestedArray) {
    if (Array.isArray(item)) {
      result = result.concat(flatten(item));
    }
    else {
	    result.push(item)
    }
  }
    return result;
};

대망의 결과

위 코드로 예제를 실행시켜 보았다.

드디어 원하는 결과인 싹 다 평탄화 된 배열을 맞이할 수 있었다.