[LeetCode] 1047, 1209 Remove All Adjacent Duplicates In String I, II JavaScript

문제 링크

Remove All Adjacent Duplicates In String - LeetCode

 

Remove All Adjacent Duplicates in String II - LeetCode

 

문제 유형

문자열, 스택

 

문제 풀이

첫번째 문제는 붙어있는 같은 문자열을 제거해 나가서 더이상 제거할 수 없을 때의 문자열을 출력하는 문제이다. 해당 문제는 괄호 검사 문제와 비슷하게 접근하면 된다. 스택을 하나 만들고, 문자열을 순회하면서 현재 문자가 스택의 top에도 존재하면 pop하고, 그렇지 않으면 스택에 현재 문자를 넣어주면 된다.

 

두번째 문제는 첫번째 문제에서 응용된 문제로, 붙어있는 같은 문자열의 길이가 k인 문자열만 제거해나가는 문제이다. 해당 문제는 출력할 문자열을 만들기 위한 스택 하나와 붙어있는 문자의 개수를 세기 위한 count 스택 2개를 만들면 O(n)의 시간 복잡도로 해결할 수 있다.

문제 접근법은 다음과 같다.

1. 일반적인 스택 1개와 붙어있는 문자의 개수를 저장할 count 스택 1개를 생성한다.
2. 문자열을 순회한다.
   2 - 1. 스택의 top 원소와 현재 문자가 같고, 문자열의 길이가 k라면 count의 top 원소 수 만큼 스택을 pop한다. 그리고 해당 문자의 개수도 pop한다.
   2 - 2. 스택의 top 원소와 현재 문자가 같은데 문자열의 길이가 k가 아니라면 스택에 해당 문자를 push하고, count의 top 원소의 개수를 하나 늘린다.
   2 - 3. 스택의 top 원소와 현재 문자가 같지 않으면 현재 문자를 스택에 push하고, 해당 문자의 개수를 count 스택에 push한다.
3. 스택을 문자열로 출력한다.
             

count 스택을 따로 만들었기 때문에 k번 같은 문자가 반복될 때, (k - 1)번의 비교없이 (k - 1)개만 count 스택에서 pop하면 되므로 이는 문자열 길이 n과 관련이 없다.

 

❗️배열, 문자열 문제를 만났을 때 정렬, 투 포인터, 이진 탐색 말고도 스택으로 접근하는 방법을 생각해보자.

 

코드

// 1047. Remove All Adjacent Duplicates In String
var removeDuplicates = function(s) {
    let stack = [s[0]];
    for (let i = 1; i < s.length; i++) {
        stack[stack.length - 1] === s[i] ? stack.pop() : stack.push(s[i]);
    }
    return stack.join("");
};

// 1209. Remove All Adjacent Duplicates in String II
var removeDuplicates = function(s, k) {
    let stack = [s[0]];
    let count = [1];
    
    for (let i = 1; i < s.length; i++) {
        if (stack[stack.length - 1] === s[i]) {
            if (count[count.length - 1] + 1 === k) { // k번 반복되는 문자일 때
                for (let j = 0; j < count[count.length - 1]; j++) { // (k - 1)번 pop
                    stack.pop();
                }
                count.pop();
            } else { // k번 반복되는 문자가 아닐 때
                stack.push(s[i]);
                count[count.length - 1] += 1;
            }
        } else { // 아예 반복되는 문자가 아닐 때
            stack.push(s[i]);
            count.push(1);
        }
    }
    
    return stack.join("");
};

 

참고

https://www.youtube.com/watch?v=EU7ISz76xjw