[JS] 프로그래머스 - 짝지어 제거하기

효율성이 관건이였던 이번문제.

처음에는 배열을 잘라가면서 중복을 제거해줬다

function solution(s)
{
    var answer = -1;
    let arr=s.split('');
    let i=0;    
    let len=arr.length;
    while(arr.length&&i!==arr.length-1){
        
        if(arr[i]===arr[i+1]){
            arr.splice(i,2); 
            i-=1;
        }else{
            i++;          
        }
        
    }        

    return arr.length?0:1;
}

자신만만하게 '제출 후 채점하기'를 누르고 정확성에서 통과되는걸 보고 만족의 미소를 짓고 있던 찰나 효율성검사에서 실패가 주루룩 떳다.

무엇이 문제였을까.

바로 저 splice함수가 문제였다.

배열은 링크드리스트와 달리 인덱스에 접근할때는 굉장히 빠르게 접근할 수 있지만 중간에 있는 원소를 삭제할때는 그 뒤에있는 원소들까지 연산을 해야 하기 때문에 시간복잡도가 높다.

그래서 push, pop함수를 이용하여 다시 문제를 풀었다

function solution(s)
{

    let arr=s.split('');
    let stack=[];
    for(let i=0;i<arr.length;i++){
     
        if(stack.length===0){
            stack.push(arr[i]);
        }else{
            if(stack[stack.length-1]===arr[i]){
            stack.pop();
            }else{
                stack.push(arr[i]);
            }
        }
        
    }
     
    return stack.length?0:1;
}

결과는

오늘의 교훈 : 효율성에 더욱더 신경을 쓰자