JavaScript로 이진 문자열의 인접 중복을 없애는 최소 삭제 횟수 구하기

이진 문자열(binary string)은 '0'과 '1'만으로 구성된 문자열입니다. 다음과 같은 이진 문자열이 있다고 가정해 보겠습니다.

const str = '001001';

우리는 이러한 문자열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

함수는 입력 문자열에서 인접한 두 문자가 서로 같지 않도록 만들기 위해 필요한 최소 삭제 횟수를 계산하여 반환해야 합니다.

문제 이해하기

위 문자열의 경우 기대하는 출력 결과는 다음과 같습니다.

const output = 2;

그 이유는 인덱스 0과 3에 있는 '0' 두 개를 삭제하면 새 문자열이 '0101'이 되어, 인접한 어떤 두 문자도 같지 않은 원하는 형태가 되기 때문입니다.

핵심 아이디어

사실 이 문제는 생각보다 간단합니다. 연속으로 같은 문자가 반복될 때마다 그중 하나는 반드시 삭제해야 합니다. 즉, 인접한 두 문자가 같은 지점의 개수가 곧 최소 삭제 횟수와 일치합니다.

구현 예제

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

const str = '001001';
const minimumDeletions = (str = '') => {
   let count = 0;
   const { length } = str;
   for(let i = 0; i < length; i++){
      if (str[i] === str[i + 1]){
         count++;
      };
   }
   return count;
};
console.log(minimumDeletions(str));

코드 설명

• 삭제 횟수를 저장할 변수 count를 0으로 초기화합니다.
• for 반복문을 사용해 문자열을 처음부터 끝까지 순회하면서 현재 문자 str[i]와 다음 문자 str[i + 1]를 비교합니다.
• 두 문자가 같다면 count를 1씩 증가시킵니다. 이는 해당 위치에서 하나의 문자를 삭제해야 함을 의미합니다.
• 순회가 끝나면 count 값을 반환합니다.

출력 결과

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

2

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 O(1) 공간 복잡도로 해결할 수 있는 매우 효율적인 방법입니다.