JavaScript로 문자열 배열의 공통 문자 추출하기: 중복 포함 방법

문제 정의

JavaScript 함수를 작성해야 합니다. 이 함수는 첫 번째이자 유일한 인수로 문자열 배열 arr를 받습니다.

함수는 배열 arr 내 모든 문자열에 공통으로 등장하는 문자들을 반환해야 하며, 이때 중복된 문자도 그대로 포함해야 합니다.

예를 들어, 어떤 문자가 모든 문자열에서 3번이 아닌 2번씩 나타난다면, 최종 결과에는 해당 문자가 정확히 2번만 포함되어야 합니다.

입력 예시

함수에 다음과 같은 입력이 주어진다고 가정해 보겠습니다.

const arr = ['door', 'floor', 'crook'];

그렇다면 출력 결과는 다음과 같아야 합니다.

const output = ['r', 'o', 'o'];

동작 원리

이 문제를 해결하는 핵심 아이디어는 다음과 같습니다.

첫 번째 문자열의 각 문자 개수를 객체에 기록합니다.
두 번째 문자열부터는 이전 결과와 비교하면서, 양쪽에 모두 존재하는 문자만 새로운 객체에 남깁니다.
모든 문자열을 순회한 후, 최종 객체에 남은 문자들을 개수만큼 결과 배열에 담아 반환합니다.

구현 코드

위 로직을 구현한 코드는 다음과 같습니다.

const arr = ['door', 'floor', 'crook'];
const findCommon = (arr = []) => {
    let prev = null;
    arr.forEach((str) => {
        const next = {};
        for(const val of str){
            if(!prev){
                next[val] = (next[val] || 0) + 1;
            }else if(prev[val]){
                prev[val] -= 1;
                next[val] = (next[val] || 0) + 1;
            };
        };
        prev = next;
    });
    const res = Object.keys(prev).reduce((acc, val) => {
        for(let i = 0; i < prev[val]; i++){
            acc.push(val);
        }
        return acc
    }, []);
    return res;
};
console.log(findCommon(arr));

실행 결과

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

[ 'r', 'o', 'o' ]

코드 설명

코드의 흐름을 단계별로 살펴보면 다음과 같습니다.

첫 번째 문자열 처리: prev가 null일 때는 각 문자의 출현 횟수를 next 객체에 누적합니다.
이후 문자열 처리: 이미 prev에 기록된 문자만 통과시키며, 동시에 prev의 카운트를 감소시켜 한 번 매칭된 문자가 중복으로 사용되지 않도록 합니다.
결과 생성: 마지막으로 reduce를 사용해 각 문자를 남은 개수만큼 결과 배열에 추가합니다.

이 방식은 시간 복잡도가 O(N × M)(N은 문자열 개수, M은 평균 문자열 길이)로 효율적이며, 중복 문자까지 정확하게 처리할 수 있다는 장점이 있습니다.