JavaScript로 두 문자열의 공통 문자 개수 구하는 방법

문제 이해하기

두 개의 문자열, 예를 들어 str1과 str2를 입력받아 두 문자열에 공통으로 존재하는 문자의 개수를 세는 JavaScript 함수를 작성해야 합니다.

여기서 말하는 '공통 문자'란 두 문자열 모두에 나타나는 문자를 의미합니다. 같은 문자가 여러 번 등장하는 경우에는 양쪽 문자열에서 등장한 횟수 중 더 적은 횟수만큼만 카운트한다는 점에 유의해야 합니다.

예시

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

const str1 = 'aabbcc';
const str2 = 'adcaa';

str1에는 'a'가 2개, 'b'가 2개, 'c'가 2개 있고, str2에는 'a'가 3개, 'd'가 1개, 'c'가 1개 있습니다. 따라서 공통 문자는 'a' 2개와 'c' 1개로 총 3개이며, 함수의 반환값은 3이 되어야 합니다.

구현 코드

다음은 위 문제를 해결하는 코드입니다.

const str1 = 'aabbcc';
const str2 = 'adcaa';

const commonCharacterCount = (str1 = '', str2 = '') => {
    let count = 0;
    str1 = str1.split('');
    str2 = str2.split('');
    str1.forEach(e => {
        if (str2.includes(e)) {
            count++;
            str2.splice(str2.indexOf(e), 1);
        };
    });
    return count;
};

console.log(commonCharacterCount(str1, str2));

출력 결과

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

코드 동작 원리

이 알고리즘은 다음 단계로 동작합니다.

1. 문자열을 배열로 변환 — split('') 메서드를 사용하여 두 문자열을 각각 문자 하나하나로 이루어진 배열로 만듭니다.

2. 문자 매칭 — forEach로 str1의 각 문자를 순회하면서 includes()로 해당 문자가 str2 배열에 존재하는지 확인합니다.

3. 중복 방지 — 공통 문자를 찾으면 카운트를 증가시키고, splice()로 str2 배열에서 해당 문자를 제거합니다. 이렇게 하면 이미 매칭된 문자가 다시 세어지는 것을 방지할 수 있습니다.

더 효율적인 대안: 빈도수 맵 활용

위 방식은 includes()와 splice()가 내부적으로 배열을 순회하기 때문에 시간 복잡도가 O(n×m)입니다. 문자열이 길어질 경우 다음과 같이 객체(빈도수 맵)를 활용하면 O(n+m)으로 성능을 크게 개선할 수 있습니다.

const commonCharacterCountOptimized = (str1 = '', str2 = '') => {
    const freq = {};
    let count = 0;

    // 첫 번째 문자열의 문자별 빈도수 계산
    for (const char of str1) {
        freq[char] = (freq[char] || 0) + 1;
    }

    // 두 번째 문자열을 순회하며 공통 문자 카운트
    for (const char of str2) {
        if (freq[char] > 0) {
            count++;
            freq[char]--;
        }
    }

    return count;
};

console.log(commonCharacterCountOptimized('aabbcc', 'adcaa')); // 3

두 방식 모두 동일한 결과인 3을 반환하지만, 입력 데이터가 클 때는 빈도수 맵 방식이 훨씬 효율적입니다. 상황에 맞게 적절한 방법을 선택하시기 바랍니다.