JavaScript 문자열에서 인접한 중복 문자 제거하기

문제 정의

JavaScript 함수는 문자열 str을 첫 번째이자 유일한 인수로 받아야 합니다.

여기서 말하는 중복 제거(duplicate removal)란 인접하면서 서로 같은 두 글자를 선택해 제거하는 작업을 의미합니다.

우리는 문자열에 대해 이러한 중복 제거를 더 이상 수행할 수 없을 때까지 반복해야 하며, 함수는 모든 중복 제거가 완료된 후의 최종 문자열을 반환해야 합니다.

예를 들어, 함수에 다음과 같은 문자열이 입력되었다고 가정해 보겠습니다.

const str = 'kllkmk';

그렇다면 기대하는 출력 결과는 다음과 같습니다.

const output = 'mk';

출력 설명

먼저 문자열에서 인접한 'll'을 제거하면 'kkmk'가 됩니다. 이어서 남아 있는 'kk'를 제거하면 최종 결과인 'mk'가 완성됩니다.

풀이 접근 방식

이 문제는 스택(Stack) 자료구조를 활용하면 간단하게 해결할 수 있습니다. 문자열의 각 문자를 순회하면서 현재 문자가 스택의 맨 위(top) 문자와 같다면 스택에서 해당 문자를 제거(pop)하고, 그렇지 않다면 현재 문자를 스택에 추가(push)합니다. 모든 문자를 처리한 뒤 스택에 남아 있는 문자들을 이어 붙이면 원하는 결과를 얻을 수 있습니다.

코드 구현

위 접근 방식을 코드로 구현하면 다음과 같습니다.

const str = 'kllkmk';
const removeDuplicates = (str = '') => {
    const arr = [];
    for(const char of str){
        if(char === arr[arr.length - 1]){
            while(arr[arr.length - 1] === char){
                arr.pop();
            };
        } else {
            arr.push(char);
        };
    };
    return arr.join('');  
};
console.log(removeDuplicates(str));

실행 결과

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

mk

이 알고리즘은 문자열의 길이 n에 대해 한 번씩만 순회하므로 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 매우 효율적입니다. 연속된 중복이 몇 겹으로 중첩되어 있어도 while 문이 이를 한 번에 처리해 주기 때문에 안정적으로 동작합니다.