5월 21일

알고리즘

짝지어 제거하기

처음의 간단한 수두코드는 아래와 같다

1. 주어진 문자열을 배열로 변경한다
2. 순회하면서 비교 index와 index+1이 같다면 그 둘을 배열에서 뺀다
3. 그후 join 메서드로 문자열을 만들어서 변수에 재할당 한다
4. 이 과정을 반복하여 배열에 아무것도 남지 않을때 Result를 Return 한다

원래코드 (실패)

function solution(s) {
  let result = s.split("")
  
  for(let i=0; i< result.length; i++){
    if(result[i] === result[i+1]){
      result.splice(i,i+1)
    }
  }
  
  return result[0]===result[1] ? 1 : 0
}

위 코드로 입출력 예제는 통과 했지만 수많은 테스트들을 실패했다 정확도도 많이 떨어지고 다른것보다 시간복잡도가 수없이 증가하여 실패하였다

리팩토링 코드 (성공)

이후 수두코드를 바꿔보기로 했다 우선 시간복잡도가 커지다 보니 자료구조를 사용해야겠다는 생각을 하면서 변경하였다

1. 비어있는 스택을 만든다
2. 순회하면서 만약 Stack의 마지막 요소와 현재 순회하고있는 문자열의 요소와 같다면 pop 시킨다
3. 그게아니라면 Stack에 집어넣는다
4. 이 과정을 반복하여 만약 Stack에 남아있는 요소가 있지 않다면 1을, 그에아니면 2를 Return 한다

function solution(s) {
  let stack = [];

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

위 코드로 테스트 및 시간복잡도를 통과했다!