재귀를 활용해 배열의 모든 위치에 요소 삽입하는 방법 – JavaScript

이번 문제에서는 insertAllPositions라는 함수를 선언해야 합니다. 이 함수는 두 개의 인자를 받습니다.

• 삽입할 요소 x
• 대상 배열 arr

함수는 배열의 배열(array of arrays)을 반환해야 하며, 각 내부 배열은 원본 배열 arr의 가능한 모든 위치에 요소 x를 하나씩 삽입한 결과여야 합니다.

즉, arr의 길이가 N이라면 결과 배열에는 N + 1개의 배열이 포함됩니다.

예시

예를 들어 insertAllPositions(10, [1,2,3])의 결과는 다음과 같아야 합니다.

const output = [
   [10,1,2,3],
   [1,10,2,3],
   [1,2,10,3],
   [1,2,3,10]
];

요구 사항은 이 함수를 오직 재귀(recursion)만 사용해서 작성하는 것입니다. 반복문(for, while 등)은 사용하지 않습니다.

코드 구현

다음은 위 조건을 만족하는 코드입니다.

const arr = [1, 2, 3];
const num = 10;
const insertAllPositions = (num, arr) => {
   return arr.length ?
   [[num, ...arr]]
   .concat(insertAllPositions(num, arr.slice(1))
   .map(el => {
      return [arr[0]].concat(el);
   })) :
   [[num]]
};
console.log(insertAllPositions(num, arr));

동작 원리

이 코드의 핵심 로직을 단계별로 살펴보겠습니다.

1. 기저 사례(Base Case): 배열이 비어 있으면(arr.length === 0) 요소를 넣을 수 있는 위치는 딱 한 곳뿐이므로 [[num]]을 반환합니다.
2. 재귀 사례(Recursive Case): 배열이 비어 있지 않다면, 먼저 현재 배열의 맨 앞에 요소를 삽입한 결과 [num, ...arr]를 만듭니다.
3. 그런 다음 첫 번째 요소를 제외한 나머지 배열(arr.slice(1))에 대해 자기 자신을 재귀 호출합니다.
4. 재귀 호출로 얻은 각 결과 배열 앞에 제외했던 첫 번째 요소(arr[0])를 다시 붙여서 최종 결과를 완성합니다.

출력 결과

위 코드를 콘솔에서 실행하면 다음과 같은 출력을 확인할 수 있습니다.

[ [ 10, 1, 2, 3 ], [ 1, 10, 2, 3 ], [ 1, 2, 10, 3 ], [ 1, 2, 3, 10 ] ]

결과를 보면 길이가 3인 배열에 요소 10을 삽입할 수 있는 4가지 위치(맨 앞, 중간 두 곳, 맨 뒤)가 모두 반영된 것을 알 수 있습니다.