[프로그래머스] 짝지어 제거하기 (Javascript)

문제링크

( https://programmers.co.kr/learn/courses/30/lessons/12973 )

분류 

 - Stack

1. 풀이 힌트

 - 알파벳 짝을 O(n)안에서 효율적으로 비교하는 방법을 생각해야 한다.

 - Stack 구조를 활용하여 풀이한다.

2. 풀이 과정

 1) 인자로 받은 string을 배열에 저장한다. 

 2) 빈 배열을 선언하고 Stack으로 활용한다.

 3) string의 길이만큼 반복문을 돌며, 짝이 다를 경우 Stack에 push하고, 같으면 Stack의 Top 위치의 알파벳을 pop한다.

 4) *효율성 점수도 있기 때문에, Stack에 push 할 때 마다 현재 Stack에 쌓인 알파벳의 수와 i번 만큼 반복문을 돌았을 때 string 배열에 남은 알파벳을 비교하여 string 배열의 알파벳이 더 적으면 반복문을 종료하고 0을 출력한다.

 -> 위와 같은 비교를 하는 이유는, 남은 알파벳으로 더이상 Stack의 모든 알파벳을 제거 할 수 없으면 짝을 지을 수 없다는 의미이므로 효율성을 위해 남은 반복문을 실행하지 않고 0을 리턴해준다.  

3. 코드 풀이

function solution(s) {
  if (s.length % 2 != 0) return 0;

  const arrStr = [...s];
  const stack = [];

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

  return 1;
}