알고리즘 문제를 풀다보면 특정 문자열에서 연속되는 문자열을 삭제해야하는 문제가 종종 있다.
다만, 연속 문자에 대한 처리 기준이 다른 경우가 많다.
필자가 경험해본 상황에 따라 어떤 방법을 사용하면 되는지 정리해보고자 한다.

예시로 사용할 문자열은 다음과 같다.

// 예시 1
"aabbccba"

// 예시 2
"aaabcccba"

이 문자열에 대해 연속되는 문자열을 지우고자 한다면 여러 기준이 생길 수 있다.

// 예시 1

// 기준 1
"aabbccba" => "bbccba" => "ccba" => "ba"

// 기준 2
"aabbccba" => "ba"

기준 1은 한번이라도 연속이 되는 상황이면 바로 삭제를 하고 다음 문자열을 확인하는 경우이다.
기준 2는 문자열 전체를 한번 살펴보고, 보이는 모든 연속 문자를 한번에 삭제하는 경우이다.

기준을 어떻게 정하느냐에 따라 과정이 달라진다는 점이 중요한 부분이다.
문제 요구 사항에 따라 방법을 다르게 해야하기 때문이다.

스택을 활용하는 방법

let test = "aabbccba";

function solution(test) {
  let stack = [];

  let splited = test.split("");

  for (let i = 0; i < splited.length; i++) {
    if (stack[stack.length - 1] === splited[i]) {
      stack.pop();

      continue;
    }

    stack.push(splited[i]);
  }

  return stack;
}

console.log(solution(test).join(""));  // "ab'

스택 구조를 활용하는 방법이다.

스택에 비어있다면 문자를 넣는다.

스택에 비어있지 않다면 스택의 가장 위에 있는 문자와 현재 문자를 비교한다.
만약, 두 문자가 같다면 연속되는 문자이므로
스택을 pop()하고, 다음 문자로 넘어간다.

위 과정을 반복하면, 최종적으로 스택에는 연속되는 문자가 제거된 문자만이 남게된다.

위 코드는 아래와 같은 방법으로도 사용할 수 있겠다.

let test = "aabbccba";


function solution(test) {
  let stringToArray = test.split("");
  let stack = [];

  for (let str of stringToArray) {
    if (str === stack[stack.length - 1]) {
      stack.pop();

      continue;
    }

    stack.push(str);
  }
  return stack;
}

console.log(solution(test).join(""));

위 방법들은 배열 형태의 입력값에도 적용할 수 있는데(필자는 예시를 문자열로 들어버렸지만),
만약, 입력 데이터가 문자열이라면 아래와 같이 사용해도 된다.

let test = "aabbccba";

function solution(test) {
  let stack = [];

  for (let str of test) {
    if (str === stack[stack.length - 1]) {
      stack.pop();

      continue;
    }

    stack.push(str);
  }
  return stack;
}

console.log(solution(test).join(""));

굳이 문자열을 배열화하지 않아도 된다는 것이다.

이렇게 연속되는 문자에 대한 제거 방법을 알아보았다!
라고 할 뻔.

예외 상황이 있다.
만약 문자열이 3자 이상 반복되면 어떨까?
스택 구조를 활용하는 방식에서는 스택 가장 위에 있는 문자와 다음에 들어오는 문자만을 고려한다.

이 방법을 3자 이상 연속 문자가 있는 데이터에 적용하면 아래와 같이 변환된다.

// 예시 2

// 기준 1
"aaabcccba" => "abcccba" => "abcba"

3자 이상 연속되는 문자가 제거되지 않는 것을 확인 할 수 있다.
즉, 위 방법은 2자까지만 연속되는 문자를 제거하는 것에만 유효하다는 것이다.

또한, 필자가 위에서 기준 2에 대해 말했는데
스택 구조를 활용하는 방법으로는 기준 2에 대한 해결책을 마련하기가 어렵다.
"한 번" 순회 할 때 연속 문자를 "모두" 찾아야하기 때문이다.
순차적으로 찾게되는 스택 구조와는 잘 맞지 않는다.

연속 문자 배열을 만들어서 사용하기

따라서 다른 방법을 고안해보았다.

let test = "aaabcccba";

function solution(test) {
  let startIndex = null;
  let endIndex = null;

  while (true) {
    let wantDeleteArr = [];

    // 문자열을 순회하면서 반복되는 부분의 데이터를 배열화하여 저장한다.
    // 예를들어, "a"라는 문자가 인덱스 0부터 2까지 반복되면
    // wantDeleteArr에 ["a", 0, 2]가 들어간다.
    for (let i = 0; i < test.length; i++) {
      if (test[i] !== test[i + 1]) {
        if (startIndex !== null) {
          endIndex = i;

          wantDeleteArr.push([test[i], startIndex, endIndex]);

          startIndex = null;
          endIndex = null;

          continue;
        }

        continue;
      }

      if (startIndex === null) {
        startIndex = i;
      }
    }

    // 연속 문자가 없으면 while문을 break한다.
    if (wantDeleteArr.length === 0) {
      break;
    }

    // 현재 문자열에 존재하는 연속 문자들을 전부 지운다.
    for (let i = 0; i < wantDeleteArr.length; i++) {
      const str = wantDeleteArr[i][0];

      const start = wantDeleteArr[i][1];

      const end = wantDeleteArr[i][2];

      const wantDeleteStr = str.repeat(end - start + 1);

      let deletedStr = test.split(wantDeleteStr);

      test = deletedStr.join("");
    }
  }

  return test;
}

console.log(solution(test));  // "a"

while 내에 for가 있어서 n^2의 시간 복잡도를 가지게 되긴하지만,
이 이상으로 방법이 생각나지 않았다.
더 좋은 방법을 찾게되면 업데이트 해보도록 하겠다.

참고 자료

e_juhee님 블로그
benomadwill님 블로그