[Javascript/PGS] Lv.2 : 짝지어 제거하기

 

https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

---

프로그래머스 레벨 2.

그냥 반복문 + substr로 풀었는데, 효율성에서 너무 오래걸림.

 

아 뭔가 문제가 있다! 라고 판단해서

방법을 생각해봤는데

스택으로 푸는게 최고의 방법인 것 같았다.

substr은 각각 O(N)이지만, push/pop은 각각 O(1)이므로 결국 문자열이 아니라 배열로 해결하는게 맞았다 ^-^

 

나의 풀이

function solution(s)
{
    var answer = 0;
    if(s.length<=1) return answer;
    let stack = [];
    stack.push(s[0]);
    for(let i=1; i<s.length; ++i){
        let b = s[i];
        if(stack.length===0) {
            stack.push(b);
            continue;
        }
        let a = stack.pop();
        if(a!==b) {
            stack.push(a);
            stack.push(b);
        }
    }
    if(stack.length===0) answer = 1;
    return answer;
}