[1일 1 알고리즘] 프론트엔드 JS 알고리즘 문제풀이 : 배열 평탄화(flatten)

임의의 레벨로 중첩되어 있는 배열을 평탄화하여 단일 중첩하는 알고리즘을 구해봅시다.

문제 예상 출력

// Single-level arrays are unaffected
flatten([1, 2, 3]); // [1, 2, 3]

// Inner arrays are flattened into a single level
flatten([1, [2, 3]]); // [1, 2, 3]
flatten([
  [1, 2],
  [3, 4],
]); // [1, 2, 3, 4]

// Flattens recursively
flatten([1, [2, [3, [4, [5]]]]]); // [1, 2, 3, 4, 5]

 

문제 풀이 전에 명확화 할 것

1. 배열에는 어떤 타입의 데이터가 포함되어 있나요? 일부 접근 방식은 특정 데이터 타입에만 적용됩니다.
2. 이 배열의 중첩 수준은 최대 얼마인가요? 수천 수준의 중첩이 있는 경우 선행 메모리 공간이 크다는 점을 감안할 때 재귀는 좋은 생각이 아닐 수 있습니다.
3. 새 배열을 반환해야 하나요 아니면 기존 배열을 변경해야 하나요?
4. 유효한 입력, 즉 배열을 가정할 수 있습니까? 일반적으로 대답은 "예"이므로 방어 프로그래밍에 시간을 낭비할 필요가 없습니다.
5. 코드가 실행되는 환경에서 ES6+를 지원하나요? 환경에 따라 액세스 가능한 메서드/네이티브 API가 결정됩니다.

팁

Array.isArray와 instanceof Array는 약간 차이가 있습니다(this article)

방법 1 : 반복(iteration)

이뮤터블한 방식으로 구현하기

export default function flatten(array) {
  while (array.some(Array.isArray)) {
    array = [].concat(...array);
  }
  return array;
}

방법 2 : 재귀(resursion)

/**
 * @param {Array<*|Array>} value
 * @return {Array}
 */
export default function flatten(array) {
  return array.reduce(
    (acc, curr) => acc.concat(Array.isArray(curr) ? flatten(curr) : curr),
    [],
  );
}

JS는 TCO가 되지 않기 때문에 재귀를 사용할 경우는 항상 조심해야함.
뒤에 generator를 사용하는 방법을 알아봄

플랫맵 메서드를 사용힐 수도 있음

export default function flatten(value) {
  return Array.isArray(value) ? value.flatMap((item) => flatten(item)) : value;
}

방법 3 : In-place Sort

면접관이 O(1) 솔루션을 물어볼 수도 있음

이 경우 기존 배열을 변형하는 알고리즘을 사용함

뮤터블한 메서드는 총 9개가 있음 pop, push, reverse, shift, sort, splice, unshift, copyWithin 및 fill임.

export default function flatten(array) {
  for (let i = 0; i < array.length; ) {
    if (Array.isArray(array[i])) {
      array.splice(i, 1, ...array[i]);
    } else {
      i++;
    }
  }
  return array;
}

방법 4 : generator

앞서 논의한 바와 같이 어레이에 수천 개의 레벨 중첩이 있는 경우 재귀적 접근 방식으로 인해 스택 오버플로가 발생할 수 있습니다.

generator를 사용하여 배열 항목을 개별적으로 생성할 수 있습니다.

제너레이터는 본질적으로 지연 평가하기 때문에 재귀적 접근 방식만큼 메모리 초기화 비용이 많이 들지 않습니다.

export default function* flatten(array) {
  for (const item of array) {
    if (Array.isArray(item)) {
      yield* flatten(item);
    } else {
      yield item;
    }
  }
}

방법 5 : Array.prototype.flat

flat array method 메서드 사용. 인터뷰어가 거의 못쓰게 할것임

export default function flatten(arr) {
  return arr.flat(Infinity);
}

방법 6 : 기타

인터뷰어가 싫어할 해결 방법들

문자로 바꿔서 ,로 split하고 숫자만 더하기

> 숫자가 아니면 어떻게 할 것인가

정규 표현식과 JSON.stringify

[,] 없앴다가 붙여서 JSON.parse

export default function flatten(array) {
  return JSON.parse('[' + JSON.stringify(array).replace(/(\[|\])/g, '') + ']');
}

출처 : 

https://www.greatfrontend.com/questions/javascript/flatten