프로그래머스 - 짝지어 제거하기 (JavaScript) : 효율성 테스트 만점받기 위한 과정..

알고리즘 입문한지 얼마 안된 나에겐 이 문제가 스택을 사용해서 푸는 문제인지 몰랐고 무식하게 풀어재낀 결과 정확성은 100%를 받았으나 효율성에서 0점을 받고 말았다.

효율성을 어떻게 줄여야하나 고민하던 중 이 문제는 stack을 사용해서 풀면 된다는 힌트를 얻어서 코드를 수정하였더니 확실히 속도면에서 차이를 느낄 수 있었다.

그러나 스택으로 바꿔서 풀어본 코드에서도 효율성 테스트 2에서 시간초과 가 나는 것을 목격하고 도대체 왜 ??? 시간 초과가 나는걸까를 다시 한번 고민하게 되었다.

첫번째 풀이

function solution(s) {
  if (s.length < 2) return 0;

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

  if (s.length > 0) return 0;
  else return 1;
}

스택을 사용하지 않고 풀어본 코드이다.
정확성 테스트는 다 맞았지만 효율성에서는 모조리 시간초과 가 발생했다.
(일단 정확성 테스트부터 매우 오래 걸린다 ㅋㅋㅋ)

효율성은 말할 것도 없이 0점.

스택으로 풀어라! 라는 힌트를 받고 다시 풀어본 두번째 풀이는 다음과 같다.

두번째 풀이

function solution(s) {
  if (s.length < 2) return 0;
  const stack = [];
  stack.push(s[0]);

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

  if (stack.length > 0) return 0;
  else return 1;
}

스택으로 만들어왔다.
아 이제 성공하겠지?! 라는 기대감 부푼 마음에 실행해보았으나, 오 첫번째 풀이보다 빠르네! 하면서 정답이겠지?~?~? 김칫국 마시고 있었는데

ㅖ?.. 왜요? 왜 시간초과? 왜째서?????????
여기서 더 줄일 수 있는 방법이 있는건가..?
아무래 봐도 스택에 넣었다 빼는 것은 고칠 방안이 생각나지 않고..
뭐라도 바꿔보자는 생각에 if-else 문을 삼항연산자로 바꿔보았다.

function solution(s) {
  let result = 0;

  if (s.length < 2) return 0;
  const stack = [];
  stack.push(s[0]);

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

  result = stack.length > 0 ? 0 : 1;
  return result;
}

와 뭐지 실환가.. 이게 되네
삼항연산자가 if else문보다 빠른거였나..
속도 차이가 꽤 나는 것을 보고 구글링도 해봤는데 삼항연산자가 연산자 여서 if-else문보다 더 빠르다는 글을 얼핏 보게되었는데 그래서 일까?..
또 어떤 글에서는 매번 삼항연산자가 빠르지는 않다고 해서 혼란스럽지만..ㅠㅠ
이번 문제의 경우엔 삼항연산자를 사용하니 효율성 테스트를 통과할 수 있었다.

아무튼 이번 알고리즘 풀이로 삼항연산자로 속도를 개선할 수도 있다는 새로운 사실을 알게되었다.