essential
essential

11. Remove Pairs

스택 자료구조를 사용한 효율적인 패턴 처리와 최종 상태를 확인

algorithm test

11. Remove Pairs

Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.161.

Problem solving

1. 스택을 이용한 접근법

function solution(s) {
  const stack = [];

  for (const c of s) {
    // ① 스택이 비어있지 않고 현재 문자와 스택의 맨 위(뒤) 문자가 같으면
    if (stack.length > 0 && stack[stack.length -1] === c) {
    // ② 스택의 모든 문자 제거
      stack.pop();
    } else {
    // ③ 스택의 현재문자 추가
      stack.push(c);
    }
  }
    // ④ 스택이 비어 있으면 1, 그렇지 않으면 0 반환
  return stack.length === 0 ? 1 : 0;
}

문자열 문제를 처음 보는 많은 사람들이 이중 반복문으로 문제를 해결하려는 경우가 많으나 문자열의 길이를 봐야 한다.
문자열의 길이가 최대 100만이므로 이중 반복문, 즉, 시간복잡도가 O(N2>)인 알고리즘으로 접근하면 무조건 시간 초과가 발생한다.

시간복잡도가 O(N)인 알고리즘을 적용해야 한다!

  • 문자열의 각 문자를 차례로 확인하면서, 중복된 문자가 있으면 스택에서 제거하고, 중복되지 않은 문자는 스택에 추가한다.
  • 모든 문자를 처리한 후, 스택이 비어 있으면 문자열이 모두 제거되었다는 의미이므로 1을 반환합니다. 그렇지 않으면 남은 문자가 있으므로 0을 반환한다.



2. 재귀적 접근법

재귀를 사용해서 인접한 중복된 문자를 반복적으로 제거하는 방법도 있다. 이 방식은 문자열을 재귀적으로 처리하며, 중복된 문자들이 제거되면 다시 남은 문자열얼 처리한다.

function recursiveSolution(s) {
  function removeAdjacent(str) {
    let newStr = '';
    let i = 0;
    while (i < str.length) {
      if (i + 1 < str.length && str[i] === str[i + 1]) {
        i += 2;  // 중복된 문자들을 건너뜀
      } else {
        newStr += str[i];
        i++;
      }
    }
    return newStr;
  }

  let result = removeAdjacent(s);
  
  // 더 이상 제거할 것이 없으면 종료
  return result === '' ? 1 : result === s ? 0 : recursiveSolution(result);
}
  • removeAdjacent 함수를 사용해 인접한 중복된 문자를 제거한 새로운 문자열을 얻는다.
  • 중복 문자가 모두 제거되어 문자열이 빈 경우 1을 반환한다.
  • 중복 문자가 더 이상 없으면 0을 반환한다.
  • 중복이 제거되었지만 문자열이 남아 있다면, 그 남은 문자열로 다시 같은 작업을 재귀적으로 반복한다. recursiveSolution(result);



3. 투 포인터 방법

투 포인터 알고리즘을 사용하여 배열을 직접 수정하면서 중복된 문자를 제거하는 방법도 가능하다. 이방식은 스택 대신 포인터를 이용하여 효율적으로 문자열을 처리한다.

function twoPointerSolution(s) {
  let arr = s.split('');
  let j = -1;  // 현재 배열의 마지막 인덱스를 추적하는 포인터

  for (let i = 0; i < arr.length; i++) {
    if (j >= 0 && arr[j] === arr[i]) {
      // 만약 포인터가 가리키는 문자와 현재 문자가 같으면, 포인터를 감소시켜 중복을 제거
      j--;
    } else {
      // 다르면 포인터를 증가시키고 그 자리에 현재 문자를 저장
      j++;
      arr[j] = arr[i];
    }
  }

  // 포인터가 -1일 때는 문자열이 모두 제거된 상태
  return j === -1 ? 1 : 0;
}
  • j 포인터는 중복되지 않은 문자의 위치를 추적하고, i 는 배열의 모든 문자를 탐색한다.
  • 중복된 문자를 만나면 j 를 줄여서 배열에서 해당 문자들을 제거하는 방식으로 동작한다.
  • 결과적으로 남은 문자가 없으면 1, 남은 문자가 있으면 0을 반환한다.



4. Reduce를 이용한 함수형 프로그래밍 스타일

Array.prototype.reduce() 를 사용한 함수형 프로그래밍 접근법도 가능하다.

function functionalSolution(s) {
  const stack = s.split('').reduce((acc, c) => {
    if (acc.length > 0 && acc[acc.length - 1] === c) {
      acc.pop();  // 현재 문자가 스택의 마지막 문자와 같으면 제거
    } else {
      acc.push(c);  // 다르면 스택에 추가
    }
    return acc;
  }, []);

  return stack.length === 0 ? 1 : 0;
}
  • 문자열을 배열로 변환한다.
  • reduce 함수를 사용하여 각 문자를 하나씩 스택에 넣거나, 중복되면 스택에서 제거한다.
  • 스택의 마지막 문자와 현재 문자가 같으면 중복된 것이므로, 스택에서 제거(pop)한다.
  • 그렇지 않으면 스택에 푸시한다.
  • 모든 문자를 처리한 후, 스택에 문자가 남아 있는지 확인하여 문자열이 모두 제거되었는지 여부를 반환한다.




Development
Algorithm