JavaScript로 문자열의 중복 문자 개수 구하기

이번 글에서는 문자열을 입력받아 해당 문자열에 포함된 중복(redundant) 문자의 개수를 반환하는 JavaScript 함수를 작성해 보겠습니다. 여기서 중복 문자란 같은 문자가 두 번 이상 나타날 때, 첫 번째 등장을 제외한 나머지 발생 횟수를 의미합니다.

문제 이해하기

예를 들어 다음과 같은 문자열이 있다고 가정해 봅시다.

const str = 'abcde';

이 문자열의 모든 문자는 한 번씩만 등장하므로, 결과는 0이 되어야 합니다.

반면 아래와 같은 문자열이라면 어떨까요?

const str = 'aaacbfsc';

여기서 'a'는 3번, 'c'는 2번 등장합니다. 즉, 'a'는 2개, 'c'는 1개가 중복이므로 결과는 3이 되어야 합니다.

해결 방법

가장 간단한 접근 방식은 각 문자에 대해 해당 문자가 마지막으로 등장하는 위치(lastIndexOf)를 확인하는 것입니다. 현재 인덱스가 그 문자의 마지막 등장 인덱스와 같다면 해당 문자는 더 이상 뒤에 나오지 않는 것이므로 건너뛰고, 그렇지 않다면 같은 문자가 뒤에 또 존재한다는 뜻이므로 카운트를 1 증가시킵니다.

코드 예제

const str = 'aaacbfsc';

const countRedundant = str => {
    let count = 0;
    for(let i = 0; i < str.length; i++){
        if(i === str.lastIndexOf(str[i])){
            continue;
        };
        count++;
    };
    return count;
};

console.log(countRedundant(str));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.

3

동작 원리 살펴보기

'aaacbfsc' 문자열을 기준으로 로직을 단계별로 확인해 보겠습니다.

- 인덱스 0의 'a': lastIndexOf('a')는 2이므로 0 !== 2 → count 1 증가
- 인덱스 1의 'a': lastIndexOf('a')는 2이므로 1 !== 2 → count 1 증가
- 인덱스 2의 'a': lastIndexOf('a')는 2이므로 continue
- 인덱스 3의 'c': lastIndexOf('c')는 7이므로 count 1 증가
- 인덱스 4~6의 'b', 'f', 's': 각각 마지막 등장 위치와 일치하므로 continue
- 인덱스 7의 'c': lastIndexOf('c')는 7이므로 continue

결과적으로 count는 3이 되며, 이는 중복된 문자의 총 개수와 정확히 일치합니다.

시간 복잡도 참고

lastIndexOf를 매 반복마다 호출하므로 시간 복잡도는 O(n²)입니다. 문자열이 매우 길다면 Map 객체를 사용해 각 문자의 등장 횟수를 미리 계산한 뒤, (전체 길이 − 고유 문자 수)를 반환하는 O(n) 방식으로 최적화할 수 있습니다.