JavaScript 배열에서 홀수 번 등장하는 요소의 마지막 발생 제거하기

다음과 같은 숫자 배열이 있다고 가정해 보겠습니다.

const arr = [1, 6, 3, 1, 3, 1, 6, 3];

우리는 이러한 배열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 그런 다음 함수는 배열에서 홀수 번(단, 딱 한 번 등장하는 경우는 제외) 등장하는 모든 숫자를 찾아야 합니다.

예시

위 배열에서 숫자 1과 3은 각각 3번(홀수) 등장합니다. 따라서 함수는 두 숫자의 세 번째 발생을 제거해야 합니다.

결과 배열은 다음과 같아야 합니다.

const output = [1, 6, 3, 1, 3, 6];

접근 방법

이 문제는 해시맵(hashmap)을 활용하면 효율적으로 해결할 수 있습니다. 각 숫자의 등장 횟수를 추적하고, 마지막에 맵을 순회하면서 홀수 번 등장한 숫자의 마지막 발생 위치를 삭제하는 방식입니다.

맵의 각 키는 배열 값을 가지며, 배열의 첫 번째 요소는 해당 숫자가 등장한 횟수, 두 번째 요소는 마지막으로 등장한 인덱스를 저장합니다.

구현 코드

const arr = [1, 6, 3, 1, 3, 1, 6, 3];
const removeOddOccurence = (arr = []) => {
    // 원본 배열이 변경되지 않도록 복사본 생성
    const copy = arr.slice();
    const map = {};
    arr.forEach((num, ind) => {
        if(map.hasOwnProperty(num)){
            map[num][0]++;
            map[num][1] = ind;
        }else{
            map[num] = [1, ind];
        };
    });
    for(const key in map){
        const [freq, index] = map[key];
        // 한 번만 등장한 경우는 제외하고, 홀수 번 등장한 경우에만 처리
        if(freq !== 1 && freq % 2 === 1){
            copy.splice(index, 1, '');
        };
    };
    return copy.filter(el => el !== '');
};
console.log(removeOddOccurence(arr));

코드 동작 원리

1. 먼저 slice()를 사용해 원본 배열을 보존한 복사본을 만듭니다.
2. forEach로 배열을 순회하며 각 숫자의 등장 횟수와 마지막 등장 인덱스를 맵에 기록합니다.
3. 맵을 순회하며 등장 횟수가 1이 아니면서 홀수인 숫자를 찾습니다.
4. 해당 숫자의 마지막 발생 위치를 빈 문자열로 대체한 뒤, filter()로 빈 문자열을 제거하여 최종 배열을 반환합니다.

출력 결과

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

[1, 6, 3, 1, 3, 6]

이 접근 방식은 배열을 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가로 맵과 복사본 배열을 저장하므로 공간 복잡도 역시 O(n)입니다. 원본 배열을 변경하지 않으면서 원하는 결과를 얻을 수 있는 안전하고 효율적인 방법입니다.