JavaScript로 배열에서 첫 번째 중복 요소 찾기

배열에서 가장 먼저 두 번 이상 등장하는 요소의 인덱스를 반환하는 함수를 작성해야 한다고 가정해 봅시다. 만약 배열에 중복된 요소가 하나도 없다면 -1을 반환해야 합니다. 또한 추가 메모리를 사용하지 않고 상수 공간(O(1)) 내에서 문제를 해결해야 한다는 조건이 있습니다.

접근 방법

이 문제를 해결하기 위해 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, 1, 1, 2, 3, 4, 4, 5]에서 인덱스 0의 값은 0이며, 이 값은 배열에서 한 번만 등장하므로 조건을 통과합니다. 그다음 인덱스 1의 값은 1인데, lastIndexOf(1)의 결과는 2입니다. 현재 인덱스 1과 다르므로, 값 1이 중복 요소임을 알 수 있고 함수는 인덱스 1을 반환하게 됩니다.

참고 사항

이 방법은 추가 자료구조를 사용하지 않아 상수 공간을 만족하지만, 각 요소마다 lastIndexOf()를 호출하기 때문에 시간 복잡도는 O(n²)입니다. 만약 성능이 중요하고 추가 메모리 사용이 허용된다면, Map이나 Set을 활용해 O(n) 시간 복잡도로 최적화할 수 있습니다.