[프로그래머스] 짝지어 제거하기 (자바스크립트/javascript/js)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12973?language=javascript 

코딩테스트 연습 - 짝지어 제거하기

 

 

 

문제를 풀기 위한 아이디어

처음에는 그냥 반복문을 돌면서 index를 가지고 index와 index+1이 같은지 비교한 후 같다면 둘을 잘라내고 index는 처음부터(0부터) 다시 반복문을 돌렸었다. index와 index+1이 같지 않다면 index를 증가시키는 방법으로 풀었었다.

그러나 시간초과가 떴고, 생각해보니 문자열의 길이가 100만개인데 최악의 경우로 100만개 가장 직전까지 비교하다가 마지막에 두개가 같아서 터지면 또 맨 처음부터 다시 비교해야 하는 걸 생각하니 시간초과가 나오는게 당연했다.

 

한 번의 반복문을 돌 때 모두 해결 할 수 있는 방법으로는 스택을 사용하면 되었다.

쉽게 말해 애니팡게임처럼 스택의 최상단 값과 그 아래의 값이 같다면 애니팡이 터지듯 사라지는 것이다.

이렇게 모든 문자열 입력을 반복문을 다 돌고나서 스택이 비어있다면 문자열이 모두 제거된 것이므로 1을 출력하고 스택에 뭐가 남아있다면 문자열이 모두 제거되지 않은 것이기 때문에 0을 출력해주면 된다.

비슷한 문제로 예전에 크레인 뽑기 게임(카카오 문제)을 푼적이 있는데 왜 스택을 처음부터 생각하지 못했나 하는 생각이 든다.

앞으로는 뭔가 중복되어 터져버리는 문제가 나오면 스택을 떠올려보아야 겠다!

 

 

 

function solution(string) {
  let answer;
  let index = 0;
    const stack = [];
    for(let i = 0; i < string.length; i++){
        stack.push(string[i]);
        if(stack[stack.length - 1] === stack[stack.length - 2]){
            stack.pop();
            stack.pop();
        }
    }
    answer = (stack.length ? 0 : 1)
  return answer;
}