[Javascript] 짝지어 제거하기 (12973)

문제링크

접근방법

문제 자체는 단순히 현재 배열 요소와 다음 배열 요소가 같으면 둘다 제거하고(splice)
제거된 배열을 다시 처음부터 비교하여 계속해서 제거하는 것이다.
b aa baa → bb aa → aa →

처음 틀린 문제는 자세히 생각해보니 if(arr[i] === arr[i+1]) 일때마다 계속해서 배열의 초기값으로 돌아가 전체를 다시 순회한다. n!이라는 매우 비효율적인 코드이다.

stack을 사용하여 for문을 한번만 순회하도록 코드를 바꾸어 풀이하였다.

 

처음 틀린 문제 ( 답은 다 맞아도 시간초과로 통과하지 못함)

function solution(s)
{
    var answer = -1;
    arr = s.split("");
    
    for(let i = 0; i < arr.length; i++){
      if(arr[i] === arr[i+1]){
        arr.splice(i, 2);
        i = -1;
      }
    }
    answer = arr.length > 0 ? 0 : 1;

    return answer;
}

 

stack을 이용하여 구한 답

function solution(s)
{
    var arr = [];
    
    for(var i=0; i<s.length; i++){
        if(arr[arr.length-1] != s[i]){
            arr.push(s[i]);
        }else{
            arr.pop();
        }
    }
    
    answer = arr.length > 0 ? 0 : 1;

    return answer;
}