재귀(Recursion)로 배열의 연속 중복 요소 제거하기 - JavaScript

이번 문제는 숫자 또는 문자열 리터럴로 이루어진 배열을 입력받아, 추가 메모리 공간을 사용하지 않고 연속으로 중복되는 요소들을 모두 제거하는 함수를 작성하는 것입니다.

문제 예시

예를 들어, 입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [17, 17, 17, 12, 12, 354, 354, 1, 1, 1];

이때 기대하는 출력 결과는 다음과 같습니다. 연속해서 반복된 값은 하나만 남기고 제거됩니다.

const output = [17, 12, 354, 1];

재귀를 활용한 해결 방법

추가 배열을 만들지 않고 제자리(in-place)에서 처리하기 위해 재귀 함수와 splice() 메서드를 활용할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 배열을 처음부터 끝까지 순회하면서 현재 위치의 요소와 다음 요소를 비교합니다.
• 두 요소가 같다면 해당 위치의 요소를 삭제하고, 인덱스를 한 칸 뒤로 물립니다.
• 삭제 여부를 나타내는 불리언 값을 재귀 호출의 인자로 전달하여 다음 단계에서 처리하도록 합니다.

다음은 전체 코드입니다.

const arr = [17, 17, 17, 12, 12, 354, 354, 1, 1, 1];

const comp = (arr, len = 0, deletable = false) => {
   if(len < arr.length){
      if(deletable){
         arr.splice(len, 1);
         len--;
      }
      return comp(arr, len+1, arr[len] === arr[len+1])
   };
   return;
};

comp(arr);
console.log(arr);

코드 동작 원리

1. comp 함수는 세 개의 매개변수를 받습니다. 대상 배열 arr, 현재 인덱스 len(기본값 0), 그리고 직전 단계에서 중복이 발견되었는지를 나타내는 deletable(기본값 false)입니다.
2. 인덱스가 배열 길이보다 작은 동안 재귀적으로 자기 자신을 호출합니다.
3. deletable이 true라면 현재 요소는 앞 요소와 중복된 것이므로 splice()로 제거하고, 인덱스를 하나 감소시켜 올바른 위치를 유지합니다.
4. 다음 재귀 호출 시에는 arr[len] === arr[len+1]의 비교 결과를 전달하여, 연속 중복 여부를 계속 추적합니다.

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 출력이 나타납니다.

[ 17, 12, 354, 1 ]

이처럼 재귀와 제자리 삭제를 조합하면 별도의 새 배열을 생성하지 않고도 연속 중복 요소를 효율적으로 제거할 수 있습니다.