[자바스크립트로 하는 자료 구조와 알고리즘] 5장 자바스크립트 배열 - 2

k개의 정렬된 배열에서 공통 항목 찾기

const arr1 = [1, 5, 5, 10];
const arr2 = [3, 4, 5, 5, 10];
const arr3 = [5, 5, 10, 20];

function commonElements(kArray) {
    var hashmap = {},
        last,
        answer = [];

    for (var i = 0, kArrayLength = kArray.length; i < kArrayLength; i++) {
        var currentArray = kArray[i];
        last = null;
        for (var j = 0, currentArrayLen = currentArray.length; j < currentArrayLen; j++) {
            var currentElement = currentArray[j];
            if (last != currentElement) {//전 인덱스의 값과 동일하다면 중복이므로 카운트하지 않기위해
                if (!hashmap[currentElement]) {
                    hashmap[currentElement] = 1;
                } else {
                    hashmap[currentElement]++;
                }
            }
            last = currentElement;
        }
    }

    for (var prop in hashmap) {
        if (hashmap[prop] == kArray.length) {
            answer.push(parseInt(prop));
        }
    }
    return answer;
}

여러 개의 배열이 주어졌을 때 모든 배열에서 공통되는 항목을 찾기 위한 코드이다. 각 배열을 순회하며 배열의 요소를 key로 하고 카운트 된 개수를 value로 하는 해시테이블을 사용한다.
공통 요소가 총 몇 개냐가 아니라 각 배열마다 공통되는 요소가 무엇이냐를 묻고있기에, 이 때 카운트 값으로 사용되는 value는 주어진 배열의 개수를 보다 클 수 없다. (주어진 배열이 3개일 경우 value == 3이면 공통 항목이다.)
그래서 [1, 5, 5, 10]처럼 같은 수가 두 번 나올 경우 중복으로 카운트 하지 않기 위해 이전 차례의 요소와 현재 차례의 요소가 같은 것인지 확인이 필요하다.

그런데 위 코드처럼 last = currentElement라고 할 경우 다음 턴에서 last는 currentElement의 전 인덱스의 값을 가지고 있다. 이럴 경우 [1, 5, 5, 10] 같이 중복되는 요소가 연속한 경우는 거를 수 있지만 [1, 5, 3, 5]처럼 연속되지 않으면 거를 수 없다.

function newCommonElements(kArray) {
    var hashmap = {},
        answer = [];

    for (var i = 0, kArrayLength = kArray.length; i < kArrayLength; i++) {
        var currentArray = kArray[i];
        last = null;
        for (var j = 0, currentArrayLen = currentArray.length; j < currentArrayLen; j++) {
            var currentElement = currentArray[j];
            console.log(currentElement, hashmap.hasOwnProperty(currentElement));
            //currentElement 키가 없다면 값을 넣고
            if (!hashmap[currentElement]) {
                hashmap[currentElement] = 1;
                //첫번째 배열을 돌고 있다면 각 키별 값은 1을 넘을 수 없고,
                //두번째 배열을 돌고 있다면 각 키별 값은 2를 넘을 수 없다.
                //최종적으로 각 키별 값은 kArray의 길이를 넘을 수 없다.
                //앞에서 이미 currentElement가 있었을 경우 ++이 되었을 것이므로 그 경우 카운트하지 않는다.
            } else if (hashmap[currentElement] < i + 1) {
                hashmap[currentElement]++;
            }
        }
    }

    for (var prop in hashmap) {
        if (hashmap[prop] == kArray.length) {
            answer.push(parseInt(prop));
        }
    }
    return answer;
}

코드를 수정해보았다. last를 사용하지 않고 hashmap의 value를 증가하는 부분을 수정했다.

else if (hashmap[currentElement] < i + 1) {
                hashmap[currentElement]++;

여기서 i + 1을 한 이유는,
앞에서 말했든 value는 주어진 배열의 개수를 넘을 수 없다. 만약 배열이 3개가 주어졌을 때 첫번째 배열을 돌고있다면 value는 1을 넘을 수 없고 두번째 배열을 돌고있다면 2를 넘을 수 없다.
인자로 주어지는 kArray는 [[ ], [ ], [ ]]처럼 이차원 배열 형태로 주어지기에 i는 배열의 인덱스를 의미하며 첫번째, 두번째 처럼 차례를 나타내기 위해서 i + 1을 해주었다.
그래서 value가 이미 현재 배열의 차례와 동일하다면 앞에서 이미 중복되는 요소가 있었다는 의미이므로 카운트를 진행하지 않도록 했다.

실행결과 :

console.log(
    "kArray : [[1, 5, 3, 5, 10], [1, 5, 5, 10], [5, 10, 2, 20]]\n",
    "result : " +
        newCommonElements([
            [1, 5, 3, 5, 10],
            [1, 5, 5, 10],
            [5, 10, 2, 20],
        ])
);