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

문제 - 링크

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

1차 답안

1. 단순히 parameter로 받은 string을 인덱스를 split하여 배열로 변환한다.
2. for문으로 돌면서 index 와 index+1 을 비교한다. 만약 이 둘이 같다면. 같다면 splice하고, Index 를 0으로 초기화 하고 처음부터 다시 비교한다.

function solution(s){
    const strArr = s.split("");

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

  return strArr.length === 0 ? 1 : 0;
}

이것도 단순하게 array method로 생각하여 풀었던것같다.
하지만, 동시에 굉장히 비효율적인 방법이라는 생각이 들었는데, 역시나 효율성테스트에서 전체 다 통과하지 못했다.

한참생각하다가, 질문하기에서 stack으로 접근하라는 어떤 분의 답변을 보고 stack을 사용했다...

고민하다가 코드를 작성하면서 깨달은건.., 이미.. 예전에 풀었던 문제였는데.. 배열로 풀었다는건.. 역시 사람은.. 망각의 동물이다.. 알고리즘 꾸준히 하자..!

2차 답안

1. stack이 비어있거나, 스택에 마지막에 있는 char가 현재 index와 같지 않다면 stack에 현재 index의 char를 Push한다.
2. stack이 비어있지 않은데, 스택의 마지막 char가 현재의 Index와 같다면 pop()을 한다.

이렇게 된다면 문자열이 모두 사라졌을 때에는 stack에 아무것도 존재하지 않을것이다.
이전 답안과 달리 for문도 한바퀴만 도므로, 시간복잡도도 확연하게 낮을것이다.

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

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

  return stack.length ? 0 : 1;
}

위 코드로 효율성 테스트도 통과하였다!