짝지어 제거하기

내 코드

function solution(s) {
    let answer = -1;
    let input = [...s]

    let word = s
    while (1) {

        for (let i = 0; i < input.length; i++) {
            let element = input[i]


            if (element === input[i + 1]) {
                input.splice(i, 2)
                if (input.length === 0) { 
                    return answer = 1
                }
                break;
            } else {
                if (i >= input.length -1) {
                    return answer = 0;
                }
            }


        }

    }

    
    return answer;
}

✓ 재귀함수로 다음 인덱스의 값이 같으면 splice하는 방법을 사용했다. ==> 시간초과 💀
✓ 그냥 함수로 다시 시도 ==> 시간초과 💀

문자의 길이가 1,000,000이하이므로 하나하나 비교해가며 제거하는 작업을 반복하는 것임..

처음부터 다시 조사할 필요 없이 같은 문자열이 나오면 제거하고 발견한 인덱스에 -1부터 다시 비교하면 되는데,,, 해결방법을 찾지 못했다..

결국 다른사람의 풀이를 참고했는데, Stack 자료구조를 이용했다.

알고보니 괄호문제랑 매우 유사했었던것... 괄호만 알파벳으로 바꾼것 뿐이였다...

참고한 코드

function solution(s) {
    let answer = -1;

    let st = [];

    for (let i = 0; i < s.length; i++) {
        if( (st.length === 0) || st[st.length  - 1] !== s[i]){
            st.push(s[i])

        }else{
            st.pop();
        }
        
    }

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