[Programmers] 짝지어 제거하기 - JavaScript

문제

프로그래머스

내 풀이 - 첫번째

function solution(s)
{
    let arr = [...s];

    while(arr.length >= 1){
        let isNothing = false;
        
        for(let i = 0; i < arr.length - 1; i++){
            if(arr[i] === arr[i + 1]){
                arr.splice(i, 2);
                isNothing = true;
                break;
            }
        }
        if(!isNothing) return 0;
    }
    return 1;
}

연속된 알파벳 2개 제거라는 것에 꽂혀서 문자열의 앞에서부터 순서대로 다음 문자열과 동일하면 제거하고, 다시 맨 처음부터 검사를 하는 방식으로 구현했다.

정확성 테스트는 통과했지만 효율성 테스트에서  시간초과

내 풀이 - 두번째

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

루프가 반복적으로 처음부터 다시 실행 되어야 할 때 스택을 고려해보자!

 

stack을 만들어서 비교 대상이(이번에 들어오는 문자) stack의 가장 위에 있는 문자와 같으면 stack의 가장 위를 제거하고, 다르다면 stack에 넣는다.

• 비교대상이 stack의 가장 위에 있는 문자와 같으면 stack의 가장 위를 제거 : 짝이 지어지는 경우
• 비교 대상이 stack의 가장 위에 있는 문자와 다르면 stack에 넣는다 : 짝이 지어지지 않는 경우

다시 말해, for문으로 배열을 돌면서 짝지어 지면 stack에서 pop하고, 아니면 push한다.

이처럼 시간 복잡도를 O(n)으로 만들었다.

 

마지막으로, stack의 길이가 있으면 1 아니면 0을 반환한다.

이때, return 문에서 다음과 같이 작성하면 효율성 검사 한 개를 통과하지 못했다. ! 연산을 사용해서 강제적으로 형변환 해줌으로써 시간 소모를 피할 수 있다.

return stack.length ? 0 : 1;