프로그래머스 짝지어 제거하기 - 자바스크립트 풀이

프로그래머스

 

💀 첫번째 시도

효율성에서 시간 초과로 탈락한 코드이다. 배열의 길이가 엄청 긴 최악의 경우, splice를 실행시키는 비용으로 시간 복잡도가 O(n^2) 나올 수 있는 코드이기 때문이다.

function solution(s){
    let arr = Array.from(s), i = 1;
    while(arr.length > 0 && i < arr.length){
        if(arr[i] === arr[i-1]) {arr.splice(i-1,2); i = 1;}
        else i++;
    }
    return arr.length === 0 ? 1 : 0;
}

 

두번째 시도 ( 정답 코드 )

시간 복잡도를 줄이기 위해서 스택을 활용하여 다시 코드를 작성하였다. 위의 코드와 달리 배열의 요소를 제거할 때 발생하는 이동 비용이 없으므로 보다 효율적으로 처리할 수 있다.

function solution(s){
    let stack = [];
    for(let x of s){
        if(stack.length > 0 && stack.at(-1) === x) {
            stack.pop();
        } else {
            stack.push(x);    
        }
    }
    return stack.length > 0 ? 0 : 1;
}

참고로 for문 내 if 조건문에서 stack.length > 0 을 넣느냐 아니냐에 따라 효율성 테스트 2번에서 갈린다.

if(stack.length > 0 && stack.at(-1) === x) // 😇
if(stack.at(-1) === x) // 👿 효율성 테스트 2번 시간 초과 발생

for문으로 문자를 하나씩 돌면서 바로 직전에 stack에 추가된 문자와 현재 문자가 같은 경우 stack에서 직전에 넣은 문자를 삭제해준다.

 if(stack.length > 0 && stack.at(-1) === x) {
	stack.pop();
}

stack의 마지막 요소와 for 문에서 현재 판단하고자 하는 문자가 같지 않은 경우는 그냥 stack에 현재 문자를 추가해준다.

else {
	stack.push(x);    
}

이 후 정답을 반환해준다.

return stack.length > 0 ? 0 : 1;