JavaScript 배열에서 가장 먼저 중복되는 요소의 인덱스 찾기

배열을 순회하면서 가장 먼저 두 번 이상 등장하는 요소의 인덱스를 반환하는 함수를 작성해야 합니다. 만약 모든 요소가 고유하다면, 즉 중복된 요소가 하나도 없다면 -1을 반환해야 합니다.

이 문제의 핵심 조건은 상수 공간(constant space)에서 해결해야 한다는 점입니다. 즉, Set이나 Map 같은 추가 메모리를 사용하지 않고 풀어야 합니다.

접근 방법

가장 간단한 방법은 for 루프로 배열을 순회하면서, 각 요소에 대해 Array.prototype.lastIndexOf() 메서드를 호출하는 것입니다.

lastIndexOf()는 해당 값이 배열에서 마지막으로 등장하는 인덱스를 반환합니다. 따라서 현재 인덱스 i와 lastIndexOf(arr[i])의 결과가 다르다면, 그 요소는 배열 내 어딘가에 중복되어 존재한다는 의미입니다. 이때 현재 인덱스를 바로 반환하면 됩니다.

예제 코드

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

const firstRedundant = arr => {
    for(let i = 0; i < arr.length; i++){
        if(arr.lastIndexOf(arr[i]) !== i){
            return i;
        };
    };
    return -1;
}

console.log(firstRedundant(arr1)); // 1

실행 결과

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

1

코드 설명

위 예제에서 인덱스 0의 값은 0으로 배열에 한 번만 등장하지만, 인덱스 1의 값인 1은 인덱스 2에도 존재합니다. 따라서 lastIndexOf(1)은 2를 반환하고, 이는 현재 인덱스 1과 다르므로 함수는 1을 반환하게 됩니다.

시간 복잡도 참고

이 방법은 추가 메모리를 사용하지 않아 공간 복잡도는 O(1)이지만, 매 반복마다 lastIndexOf()가 배열 전체를 탐색할 수 있으므로 시간 복잡도는 O(n²)입니다. 배열 크기가 작거나 메모리 제약이 우선인 상황에 적합한 접근 방식입니다.