이번 문제는 문자열을 인수로 받아, 해당 문자열에 포함된 중복 문자(redundant characters)의 개수를 반환하는 JavaScript 함수를 작성하는 것입니다.
문제 이해하기
예를 들어, 다음과 같은 문자열이 주어졌다고 가정해 보겠습니다.
const str = 'abcde';
'abcde'는 모든 문자가 한 번씩만 등장하므로, 출력 결과는 0이어야 합니다.
반면, 다음과 같은 문자열이 있다면:
const str = 'aaacbfsc';
여기서 'a'는 3번, 'c'는 2번 등장합니다. 각 문자가 처음 등장한 것은 정상적인 경우로 보고, 이후 반복해서 등장한 문자만 중복으로 계산하면 'a'가 2번, 'c'가 1번 추가로 등장했으므로 출력 결과는 3이 됩니다.
해결 접근 방식
이 문제는 lastIndexOf() 메서드를 활용하여 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 문자열을 순회하면서 현재 문자의 마지막 등장 위치(
lastIndexOf)와 현재 인덱스를 비교합니다. - 두 값이 같다면 해당 문자가 마지막으로 등장한 것이므로 건너뜁니다(
continue). - 두 값이 다르다면 같은 문자가 뒤에 더 존재한다는 의미이므로, 중복 횟수를 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 증가 (count = 1)
- 인덱스 1 ('a'): lastIndexOf('a')는 2이므로 1 !== 2 → count 증가 (count = 2)
- 인덱스 2 ('a'): lastIndexOf('a')는 2이므로 2 === 2 → 건너뜀
- 인덱스 3 ('c'): lastIndexOf('c')는 7이므로 3 !== 7 → count 증가 (count = 3)
- 인덱스 4~6 ('b', 'f', 's'): 각각 마지막 등장이므로 건너뜀
- 인덱스 7 ('c'): lastIndexOf('c')는 7이므로 건너뜀
결국 각 문자의 마지막 등장만 제외하고 나머지 반복 등장이 모두 카운트되어 최종 결과 3이 반환됩니다.
마무리
이 방식은 별도의 객체나 Map 없이 lastIndexOf() 하나만으로 중복 여부를 판단할 수 있다는 장점이 있습니다. 다만 문자마다 매번 문자열 전체를 탐색하므로 시간 복잡도는 O(n²)입니다. 문자열이 매우 길다면 객체(Object)나 Map을 사용해 각 문자의 등장 횟수를 한 번의 순회(O(n))로 집계하는 방식을 고려해 볼 수 있습니다.