[프로그래머스] level.2 짝지어 제거하기

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

프로그래머스

 

 

 

나의 풀이

 

function solution(s){
        let stack =[]
        for(i=0;  i <= s.length ; i++) stack[stack.length - 1] === s[i] ? stack.pop() :stack.push(s[i])
    return stack.length ? 0 : 1
}

 

처음 풀이

function solution(s){
        let divide = s.split("")
    function result(divide,box, i){
        if(divide.length === 0) return 1;
        if(divide.length === i) return 0;
        if(box[0] === divide[i]){
          divide.splice(i-1,2)
            i = 0
            box = []
        } 
        box[0] = divide[i]
        ++i
        return result(divide,box, i)
    }
    return result(divide,[],0)
}

처음에 이렇게 풀었는데 2~8번까지인가?  런타임 에러가 떴다. 

질문하기 보니까 재귀로 푼 분들은 에러가 발생한다는 것을 알게 되었다. 

문자열 길이가 1,000,000이하의 자연수이기에 재귀는 지양해야할 것 같다. 

 

그러다 스택으로 풀면 간단하다는 것을 다른 블로그글을 보고 알았다. 

 

출처 : https://movingmountain.tistory.com/208

이런식으로 하나하나 push를 해주다가 문자열의 i번째 값이 stack에 마지막으로 push했던 값과 같으면 stack에 마지막 값을 pop해주면 된다. 

이렇게 해서 stack에 문자가 남아있으면 0을 리턴 비어있으면 1을 리턴하면 정답이다.