[JS] 짝지어 제거하기

 

 

난이도: Lv.2

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

프로그래머스

 

 

알고리즘

스택 맨 위에 있는 문자와 현재 넣을 문자가 일치하면 스택 맨 위에 있는 문자를 삭제하고 현재 문자를 넣지 않는다.

문자열의 모든 문자에 대해 수행한 후 스택에 문자가 남아있으면 결과값이 0, 남아있지 않으면 결과값 1을 반환한다.

 

 

코드

function solution(s) {
    if (s.length % 2 === 1) { return 0; }

    const stack = [];
    let stack_idx = 0;
    stack.push(s[0]);

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

    if (stack_idx === -1) { return 1; }
    else { return 0; }
}

 

 

주저리

처음에는 정규표현식으로 했는데 똑같은 문자 반복되는 것을 찾는 정규표현식이 뭔지 몰라서 오만 문서를 다 뒤지다가 겨우 찾아내서 했는데 정확성이랑 효율성 둘 다 박살났다. 아래는 정규표현식으로 짠 코드이다.

function solution(s) {
    if (s.length % 2 === 1) { return 0; }

    while (true) {
        let lastLen = s.length;
        s = s.replace(/([a-z])\1+/g, '');
        let currLen = s.length;
        if (lastLen === currLen) { break; }
    }

    if (s.length === 0) { return 1; }
    else { return 0; }
}

 

효율성이야 그렇다쳐도 정확성이 왜 박살났는지는 잘.......모르겠다......... 정말 샷건 치고싶었지만 난 어른이니까 참고 질문하기를 들어가서 효율성 어쩌고 하는 글을 보다가 스택으로 풀어야 한다는 것을 꺠달았다. 킹받게도 자바스크립트에는 스택이 없기 때문에 배열로 유사 스택처럼 문제를 풀었다.