JavaScript로 배열에서 가장 긴 중첩 집합의 길이 찾기

문제 이해하기

숫자 배열 arr를 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다.

길이가 N인 배열 arr에는 0부터 N-1까지의 모든 정수가 포함되어 있습니다. 우리 함수는 다음 규칙에 따라 집합 S의 최대 길이를 찾아 반환해야 합니다.

집합 S[i] = {A[i], A[A[i]], A[A[A[i]]], ...} 형태로 정의됩니다. 즉, 첫 번째 요소는 인덱스 i에 해당하는 A[i]로 시작하고, 다음 요소는 A[A[i]], 그다음은 A[A[A[i]]] 순서로 이어집니다. 이 과정은 집합 S 안에 중복된 요소가 나타나기 직전까지 계속됩니다.

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

const arr = [5, 4, 0, 3, 1, 6, 2];

그렇다면 출력 결과는 다음과 같아야 합니다.

const output = 4;

출력 설명

배열의 각 값을 살펴보면 다음과 같습니다.

A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

가장 긴 집합 중 하나는 다음과 같습니다.

S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

인덱스 0에서 시작하면 값 5 → 인덱스 5의 값 6 → 인덱스 6의 값 2 → 인덱스 2의 값 0으로 이어지며, 다시 인덱스 0으로 돌아오므로 총 4개의 요소를 가진 집합이 됩니다.

풀이 접근 방식

이 문제의 핵심은 방문 여부 추적(visited tracking)입니다. 한 번 탐색한 인덱스는 이미 해당 사이클에 포함되어 있으므로 다시 탐색할 필요가 없습니다. 이를 활용하면 모든 요소를 한 번씩만 방문하면서 O(N) 시간 복잡도로 문제를 해결할 수 있습니다.

재귀 함수를 사용하여 각 사이클의 길이를 세고, 그중 최댓값을 반환하는 방식으로 구현합니다.

예제 코드

다음은 전체 구현 코드입니다.

const arr = [5, 4, 0, 3, 1, 6, 2];

const arrayNesting = (arr = []) => {
   const visited = {};
   const aux = (index) => {
      if (visited[index]) {
         return 0;
      }
      visited[index] = true;
      return aux(arr[index]) + 1;
   };
   let max = 0;
   arr.forEach((n, index) => {
      if (!visited[index]) {
         max = Math.max(max, aux(index));
      }
   });
   return max;
};

console.log(arrayNesting(arr));

코드 설명

visited 객체는 이미 탐색한 인덱스를 기록하여 중복 탐색을 방지합니다.
aux 함수는 재귀적으로 다음 인덱스를 따라가며 사이클의 길이를 계산합니다.
forEach 루프에서 아직 방문하지 않은 인덱스에 대해서만 탐색을 시작하고, 그 결과와 현재 최댓값을 비교합니다.

출력 결과

콘솔 출력 결과는 다음과 같습니다.

시간 및 공간 복잡도

시간 복잡도: O(N) — 각 인덱스는 정확히 한 번만 방문됩니다.
공간 복잡도: O(N) — 방문 여부를 저장하는 객체와 재귀 호출 스택이 사용됩니다.