1209. Remove All Adjacent Duplicates in String II

💡 풀이

// O(N)
var removeDuplicates = function (s, k) {
  let stack = [];
  let numStack = [];

  for (let i = 0; i < s.length; i++) {
    if (stack[stack.length - 1] === s[i]) {
      stack.push(s[i]);
      numStack[numStack.length - 1]++;
    } else {
      stack.push(s[i]);
      numStack.push(1);
    }

    if (numStack[numStack.length - 1] === k) {
      let target = k;
      while (target > 0) {
        stack.pop();
        target--;
      }
      numStack.pop();
    }
    // console.log('stack: ', stack);
    // console.log('numStack: ', numStack);
  }

  return stack.join('');
};

📝 정리

시간복잡도는 O(k*N), 즉 O(N)이다. stack을 이용해 해결하였다. 문제의 요점은 k개 동안 요소가 중복된다면, 해당 요소를 제거해야 된다는 의미이다.

k가 2일때는 stack.top과 s[i]가 같은지 비교해서 같다면 pop만 해주면 됐는데, k가 3,4,5 이런식이 되는 경우는 좀 더 복잡해진다. 일단 나는 numStack 이라는 요소의 개수를 담는 stack을 하나 더 사용했다.

위 그림처럼 s = 'abbcddd', k=3 이라고 주어졌다고 생각해보면, 왼쪽이 요소를 저장하는 stack, 오른쪽이 요소의 개수를 저장하는 numStack이 될 것이다.

• 일단 기본적으로 stack 배열에 s[i]를 loop을 돌 때마다 push해준다.

• 그리고 중복을 체크하는 if (stack[stack.length - 1] === s[i]) 코드를 작성해준다. 중복이 아닌 요소라면 numStack에 1을 push 해준다.

• 만약 numStack의 꼭대기 요소(이하 numStack.top)가 k와 같아지는 순간이 오면, k번 만큼 stack.pop()을 통해 k번 중복한 해당 요소를 모두 제거해준다. 또한, numStack에서도 pop을 통해 k번 중복이 된 해당 꼭대기 숫자를 제거해준다.

• 마지막으로 string 형태로 return 해야 되기 때문에 join('')을 사용해 배열을 string으로 변환해준다.

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

LeetCode GitHub

https://github.com/tTab1204/LeetCode