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

문제설명 : 

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

 

 

 

나의 첫번째 풀이 : 

function solution(s){
    const str = [...s]
    const stack = []
    let answer = -1;

    str.forEach((el) => {
        if(stack.length === 0) stack.push(el)
        else if(stack[stack.length - 1] == el) {
                stack.pop()
        }else {
            stack.push(el)
        }
    })

    return answer = stack.length ? 0 : 1;
}

 

이렇게 풀었더니 정확성 테스트는 모두다 통과했는데, 효율성 테스트 2,6번에서 시간 초과가 났다. 

아무리 생각해도 나의 풀이는 O(n)인것 같았는데, 뭐가 문제일까. 

 

 

 

나의 두 번째 풀이 : 

function solution(s){
    const str = [...s]
    const stack = []

    for(const x of str){
        if(stack.length === 0) stack.push(x)
        else if(stack[stack.length - 1] == x) {
                stack.pop()
        }else {
            stack.push(x)
        }
    }

    return stack.length ? 0 : 1
}

헐... for문을 사용했더니 효율성에서 통과했다. 

나는 forEach와 for문의 속도가 그렇게 차이가 없는 줄 알았는데, 

이게 영향이 있을 줄은 몰랐다. 

 

이게 통과되는 것을 보고 검색을 해보니 반복문마다 속도가 달랐다. 

가장 속도가 빠른 것은 for문. 

순서는 다음과 같다. 

for loop > reduce > forEach > map 

 

출처 : 

https://gurtn.tistory.com/121

 

 

 

나의 풀이 : 

그러면 이 문제를 어떤 접근 방법으로 풀었는지 설명해보겠다. 

 

1.모든 문자열을 탐색한다. 

2.앞뒤를 비교해 똑같으면 제거한다. 

 

나는 이 문제를 풀 때 stack을 사용하기로 했다. 

 

문자열을 탐색하면서 나오는 문자 하나하나마다 stack에 담아준다.

그리고 stack에 담을 때마다, stack의 마지막에 있는 문자열과 비교를 해서 

두 개의 문자열이 같다면 마지막에 있는 문자열을 제거하고, 

현재 들고 있는 문자는 그냥 넣지 않는다. 

 

이런식으로 stack 에 담아나가다가, 아무것도 남지 않게되면 

해당 문자열은 성공이라고 할 수 있다. 

 

 

 

다른 사람의 풀이 : 

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;
};

다른 사람이 푼 풀이이다. 

문제를 풀어나가는 논리는 나와 똑같다고 볼 수 있지만, 

중간중간에 속도를 고려한 부분이 눈에 들어와 가져왔다. 

 

1)홀수인 문자열의 경우 무조건 틀렸으므로 계산을 할 필요가 없다. 

=>   if (s.length % 2 != 0) return 0;

 

2)문자열을 탐색하는 빠른 방법이 있다 

=>     const b = s.charAt(i);

str[i] 보다 str.charAt(i) 가 더 빠르다. 

 

참고 : 

https://stackoverflow.com/questions/27144918/why-str-charati-is-1-6-times-faster-than-stri-in-node-js

---

느낀점 : 

1) 가독성을 위해서는 forEach 문이 좋을지 모르지만, 

속도면에서는 for문이 더 빠르다. 

 

2) 문자열을 탐색하는 더 빠른 방법이 있다. charAt

 

3) 아예 고려대상이 안되는 테이스는 애초에 return 시켜버리기