프로그래머스: 짝지어 제거하기

✍ 나의 풀이 1

function solution(s){
    const newArr = s.split('')

     for(let i = 0; i < newArr.length; i++){
        if(newArr[i] === newArr[i+1]){
             newArr.splice(i, 2)
             i = -1
         }
     }
     return newArr.length ? 0 : 1
 }

• 문자열 s를 배열로 변환해 newArr 상수에 할당
• newArr의 앞, 뒤 요소가 같다면 splice함수를 통해 제거하고, 다시 i = 0 부터 시작

풀이의 문제점
테스트케이스의 문자열이 짧다면 무리없이 실행되겠지만, 길이가 1,000,000이라면 같은 요소를 만나면 다시 처음으로 돌아가는 방식은 상당히 무리가 된다.

 function solution(s){
     const newArr = s.split('')

     function recur(arr){
         for(let i = 0; i < arr.length; i++){
             if(arr[i] === arr[i+1]){
                 arr.splice(i, 2)
             }
         }
     }

     recur(newArr)

     return newArr.length ? 0 : 1
 }

그래서 재귀함수를 사용해봤다. 몇몇 런타임에러나는 경우는 뭐가 잘못된건지 파악못했지만, 확실히 통과하는 케이스는 빠르게 통과한다. 하지만 효율성에서는 꽝이었다. 여전히 반복문을 처음부터 시작하는 건 똑같아서 그런듯하다.

그래서 스택으로 풀이하는 여러 답안을 봤다.

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

• 우선 문자열 길이가 홀수라면 최종 반환값 또한 홀수이기 때문에 미리 리턴한다.
• stack 이라는 빈배열을 선언과 동시에 할당한다.
• 조건의 결과에 따라 push, pop을 해서 반복문을 처음부터 돌리는 비효율을 범하지 않는다.