배열에서 중복 찾기

문제 🤔?

정수 배열을 받아 모든 중복 요소를 반환하는 함수를 작성하세요.

샘플 데이터 세트

let sampleData = [54,32,5,11,35,32,17,3,3,22,4,1,6,11];

예상 수익

[ 32, 3, 11 ]

접근법 #1 - 무차별 대입

반복되는 요소를 담을 배열을 만들어 봅시다.

    let repeatedElements = [];

다음으로 배열을 반복합니다.

    // This is also known as O(n) in Big-O notation since
    // we have to iterate over all of the items in the array
    for(let i = 0; i < sampleData.length; i++) {

    }

루프 내부에서 다시 루프를 수행하고 각 정수를 배열의 다른 모든 정수와 비교하여 중복 여부를 확인해야 합니다.

    for(let i = 0; i < sampleData.length; i++) {
        // Added for clarity, not needed since we can access
        // sampleData[i] directly in our next loop.
        let item = sampleData[i];

        // Now we need to loop over the array again to see if
        // we find the same item again.
        // 
        // Unfortunately this adds O(n^2) complexity 😢
        for (ii = 0; ii < sampleData.length; ii++) {

            // Is it the same integer in a different position?
            if ( (item === sampleData[ii]) && (i !== ii) ) {

                // Add to our array so we can return.
                repeatedElements.push(item)
            }
        }
    }

전체 코드는 다음과 같습니다 👇

let sampleData = [54,32,5,11,35,32,17,3,3,22,4,1,6,11];

function FindDuplicatesUsingBruteForce(sampleData) {

    let repeatedElements = [];

    for(let i = 0; i < sampleData.length; i++) {

        let item = sampleData[i];    
        for (ii = 0; ii < sampleData.length; ii++) {
            if ( (item === sampleData[ii]) && (i !== ii) ) {
                repeatedElements.push(item)
            }
        }
    }

    return repeatedElements;
}

console.log(FindDuplicatesUsingBruteForce(sampleData));

// returns: [ 32, 11, 32, 3, 3, 11 ]
// It actually returns items more than once, but
// I'll ignore this for now.

솔직히 말해서, 우리는 모두 비슷한 코드를 작성했습니다 🤷‍♂️. 이렇게 하면 원하는 결과를 얻을 수 있지만 리소스를 가장 많이 차지하는 가장 느린 경로입니다 🤦‍♂️.

이것은 대부분 내부 루프 때문이며 알고리즘을 O(n^2)로 바꿉니다.

데이터 세트가 작으면 차이를 느끼지 못하지만 속도가 빠르게 느려지고 💣.

이 접근 방식을 사용하지 마십시오 🛑.

접근법 #2 - 어레이 사용

이제 약간 다른 접근 방식을 시도해 보겠습니다. 추가 배열을 사용하여 내부 루프를 피할 것입니다. 이 방법이 더 효율적일 수도 있고 그렇지 않을 수도 있습니다.

이 추가 배열은 이미 본 항목을 추적합니다.

    let uniqueElements = [];
    let repeatedElements = [];

다음은 다른 모든 접근 방식에 사용할 첫 번째 접근 방식과 동일한 루프입니다.

    for(let i = 0; i < sampleData.length; i++) {

    }

루프 내에서 이미 본 👀 항목을 추적해야 합니다.

    for(let i = 0; i < sampleData.length; i++) {

        // This is where it starts to get interesting. If
        // we have already seen this number we will add it
        // to our array of duplicated elements.
        //
        // What is the Big-O complexity of Array.includes?
        // I'll come back to this.
        if (uniqueElements.includes(sampleData[i])) {
            repeatedElements.push(sampleData[i]);
        }

    }

게다가 새로운 아이템 🔍.

    for(let i = 0; i < sampleData.length; i++) {

        if (uniqueElements.includes(sampleData[i])) {
            repeatedElements.push(sampleData[i]);
        } else {
            // Add to our unique elements to track items we have 
            // already seen
            uniqueElements.push(sampleData[i]);
        }

    }

전체 코드는 다음과 같습니다 👇

let sampleData = [54,32,5,11,35,32,17,3,3,22,4,1,6,11];

function FindDuplicatesUsingArrays(sampleData) {

    let uniqueElements = [];
    let repeatedElements = [];

    for(let i = 0; i < sampleData.length; i++) {

        if (uniqueElements.includes(sampleData[i])) {
            repeatedElements.push(sampleData[i]);
        } else {
            uniqueElements.push(sampleData[i]);
        }

    }

    return repeatedElements;
}

console.log(FindDuplicatesUsingArrays(sampleData));

// returns: [ 32, 3, 11 ]

이것은 우리의 이전 접근 방식보다 더 효율적으로 보이고 그럴 수도 있지만 모두 uniqueElements.includes 🤔에 달려 있습니다.

왜요? 우리는 배열에서 항목의 선형 검색인 includes의 자바스크립트 구현에 의존하고 있습니다.

데이터 구조가 작동하는 방식으로 돌아가면 키/위치로 항목을 조회하면 배열이 매우 효율적O(1)이지만 값으로 항목을 조회하면 매우 비효율적O(n)임을 기억할 것입니다. 값 🤦‍♂️을 찾을 때까지 배열을 탐색해야 합니다.

첫 번째 접근 방식보다 더 효율적입니까? 네, 하지만 더 좋은 방법이 있습니다.

보너스: 자바스크립트의 Array는 Array 🙃가 아닙니다.

접근법 #3 - Map() 사용

또 무엇을 시도할 수 있습니까? O(1) 조회가 있는 데이터 구조는 무엇입니까? 해시테이블 😎.

    // As with a lot of things in JavaScript a Map isn't exactly a 
    // HashTable, but it's close enough for this problem.
    let uniqueElements = new Map();
    let repeatedElements = [];

uniqueElements.includes 대신 지도의 uniqueElements.has 방법을 사용합니다.

    for(let i = 0; i < sampleData.length; i++) {

        // Since a HashTable lookup is O(1) we have greatly improved
        // our performance by just using a different data structure!!!
        if (uniqueElements.has(sampleData[i])) {
            repeatedElements.push(sampleData[i]);
        } else {
            uniqueElements.set(sampleData[i], sampleData[i]);
        }

    }

전체 코드는 다음과 같습니다 👇

let sampleData = [54,32,5,11,35,32,17,3,3,22,4,1,6,11];

function FindDuplicatesUsingMap(sampleData) {

    let uniqueElements = new Map();
    let repeatedElements = [];

    for(let i = 0; i < sampleData.length; i++) {

        if (uniqueElements.has(sampleData[i])) {
            repeatedElements.push(sampleData[i]);
        } else {
            uniqueElements.set(sampleData[i], sampleData[i]);
        }

    }

    return repeatedElements;
}

console.log(FindDuplicatesUsingMap(sampleData));

// returns: [ 32, 3, 11 ]

그렇다면 이 접근 방식은 얼마나 빠릅니까? 해보고 비교해보자👇

let sampleData = [];

// 50k array of random numbers
for (let i = 0; i < 50000; i++) {
    sampleData[i] = Math.floor((Math.random() * 50000) + 1);
}

/*
 Add here the 3 functions we just looked at
 */

// Let's run them all on the same array and time it.

console.time("FindDuplicatesUsingBruteForce");
FindDuplicatesUsingBruteForce(sampleData);
console.timeEnd("FindDuplicatesUsingBruteForce");

console.time("FindDuplicatesUsingArrays");
FindDuplicatesUsingArrays(sampleData);
console.timeEnd("FindDuplicatesUsingArrays");

console.time("FindDuplicatesUsingMap");
FindDuplicatesUsingMap(sampleData);
console.timeEnd("FindDuplicatesUsingMap");

결과 👇

편집: 이 문제에 대한 수십 가지 솔루션이 있으며 여기에 설명된 것보다 공간 또는 시간 측면에서 더 효율적인 솔루션이 있습니다. 공유를 원하시는 분은 댓글로 신청해주세요👇