[JavaScript/알고리즘] OddOccurrencesInArray (feat. Map)

Lesson 2 (Arrays) - OddOccurrencesInArray(Easy)

Test results - Codility

점수: 55/100

 

홀수로만 이루어진 숫자 배열이 주어지고, 거기서 하나의 요소를 제외하면 전부 자신과 같은 값을 가진 요소가 하나씩 있어서 짝이 지어집니다. 예를 들면 [3, 5, 7, 7, 3] 이라는 배열이 있을 수 있겠네요. 거기서 홀로 남은 요소(여기선 5)를 반환하는 문제입니다.

 

.............

 

초기 코드 (실패)

function solution(A) {
    const classifiedNums = {};

    // 분류
    for (num of A) {
        if (!classifiedNums[num]) {
            classifiedNums[num] = 0;
        }

        classifiedNums[num]++;
    }
    
    console.log(classifiedNums);    // {"3": 2, "2": 1, "7": 2}

    return Number.parseInt(Object.keys(classifiedNums).find(num => 
        classifiedNums[num] === 1
    ));
}

 

최대 2n번의 작업을 하는 코드입니다. 시간복잡도는 O(n) 이겠군요.

 

이후 시간복잡도를 줄이기 위해 아래와 같이 객체 안에 이미 키가 존재한다면 해당 프로퍼티를 지우는 방법을 써봤지만 타임아웃이 일어나는 건 똑같았습니다.

Test results - Codility

 

개선 1 (실패-타임아웃)

function solution(A) {
    const classifiedNums = {};

    // 분류
    for (num of A) {
        if (!classifiedNums[num]) {
            classifiedNums[num] = 0;
            classifiedNums[num]++;
        } else if (classifiedNums[num] === 1) {
            delete classifiedNums[num];
        } else {
            classifiedNums[num]++;
        }
    }
    
    return Number.parseInt(Object.keys(classifiedNums)[0]);
}

타임아웃이 발생하는 이유는 정확하게는 알 수 없지만, classifiedNums라는 객체를 해시(key-value) 테이블처럼 사용하는 과정에서 메모리의 사용량이 늘어났을 수도 있겠습니다.

 

그래서 객체를 사용하는 대신, Map 자료구조를 사용해서 성능을 최적화하는 것이 권장됩니다.

 

개선 2 (성공)

function solution(A) {
    const classifiedNums = new Map();

    for (num of A) {
        if (classifiedNums.has(num)) {
            classifiedNums.delete(num, 1);
        } else {
            classifiedNums.set(num, 1);
        }
    }
    
    return [...classifiedNums.keys()][0];
}

이러면 타임아웃도 없어집니다. 코드도 더 깔끔해졌군요.

 

 

(+)

이 문제를 푸는 정석적인 방법은 비트 연산의 XOR 연산을 사용하는 것입니다.

XOR 연산은 같은 값이 들어오면 두 값이 모두 사라지는 특성이 있어서, 배열의 모든 숫자에 XOR 연산을 적용하면 짝이 없는 숫자만 남게 됩니다. (솔로천국 커플지옥)

자바스크립트에서는 ^= 연산자로 가능합니다.