문제 정의
문자열 'A', 'B', 'C' 세 종류의 문자만으로 구성된 문자열이 주어졌을 때, 인접한 두 문자가 서로 같지 않도록 만들기 위해 제거해야 하는 문자의 최소 개수를 구하는 JavaScript 함수를 작성해야 합니다.
예를 들어 "ABBABCCABAA"라는 문자열에서 연속으로 반복되는 문자(BB, CC, AA)를 적절히 제거하면, 모든 인접 문자 쌍이 서로 다른 상태가 됩니다.
접근 방법
가장 직관적인 해결 방법은 문자열을 처음부터 끝까지 순회하면서 현재 문자와 바로 다음 문자가 같은 경우 해당 문자 하나를 제거하고 카운트를 증가시키는 것입니다. 배열에서 요소를 제거하면(splice) 뒤의 요소들이 앞으로 당겨지므로, 인덱스를 한 칸 뒤로 물려서(i -= 1) 다시 검사하면 됩니다.
이 방식은 각 위치에서 중복된 문자를 하나씩만 남기고 나머지를 제거하기 때문에, 결과적으로 최소 제거 횟수와 일치합니다.
코드 예시
const str = "ABBABCCABAA";
const removeLetters = (str = '') => {
const arr = str.split('');
let count = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] === arr[i + 1]) {
count += 1;
arr.splice(i, 1);
i -= 1;
}
}
return count;
};
console.log(removeLetters(str));
출력 결과
3
동작 원리 상세 설명
입력 문자열 "ABBABCCABAA"를 단계별로 살펴보면 다음과 같습니다.
먼저 인덱스 1~2의 BB에서 'B' 하나를 제거하고(카운트 1), 그다음 CC에서 'C' 하나를 제거하고(카운트 2), 마지막에 연속된 AA에서 'A' 하나를 제거합니다(카운트 3). 최종적으로 문자열은 "ABABACA"처럼 인접한 모든 문자가 서로 다른 형태가 되며, 총 제거 횟수는 3입니다.
성능 참고 사항
위 코드는 splice를 사용할 때마다 배열 전체가 재배열되므로 시간 복잡도가 최악의 경우 O(n²)입니다. 더 효율적인 대안은 제거할 문자를 실제로 삭제하지 않고, 연속된 동일 문자 그룹마다 (그룹 길이 − 1)씩 카운트를 누적하는 방식입니다. 이 경우 O(n)의 시간 복잡도로 해결할 수 있습니다.