프로그래머스 짝지어제거하기 js

프로그래머스 짝지어제거하기

---

같은 알파벳이 연속하게 존재하면 반복되는 알파벳을 지우고 이를 계속 반복한다.

baabaa가 인풋으로 들어올 때 b "aa" baa가 반복되므로 해당 알파벳을 지운다

bbaa가 되므로 "bb"가 반복된다. 이를 지우고 마지막으로 aa도 지운다.

최종적으로 남는 알파벳이 없으면 1을 리턴, 남으면 0을 리턴한다.

괄호 찾기 문제랑 유사하기에 스택을 생각해서 풀었다.

스택의 최상단 값이랑 다음에 들어올 값이랑 같을 때 스택에서 pop하고, 다르면 Push하여

스택의 길이가 1이상이면 0리턴, 0이면 1을 리턴하도록 했다.

function solution(s) {
  var answer = 0;
  let len = s.length;
  let stk = [];
  for (let i = 0; i < len; i++) {
    let top = stk.length - 1;
    if (stk[top] === s[i]) {
      stk.pop();
    } else {
      stk.push(s[i]);
    }
  }
  return stk.length >= 1 ? 0 : 1;
}

예시를 이용해 설명하자면,

초기 stk은 비어있어서 b가 push된다.[b]

다음 반복문에서 들어올 값은 'a'다.

스택의 최상단은 현재 b이므로 a가 Push된다. [ba]

최상단은 a, 다음에 올 값은 a이므로 pop한다. [b]

...해당 과정을 반복한다.