올바른 괄호

올바른 괄호

2020.07.31

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

  const arrOfInput = s.split("");
  const limit = arrOfInput.length;
  for (let i = 0; i < limit; i++) {
    const char = arrOfInput[i];
    if (char == "(") {
      stack.push(0);
    } else {
      if (stack.length == 0) {
        return false;
      }
      stack.pop();
    }
  }
  if (stack.length != 0) {
    return false;
  }
  return true;
};

• 스택으로 푸는 가장 대표적인 문제라서 알고 풀었다.

• 다른 사람의 풀이가 더 실행 시간이 적게 걸려 참고해서 재구성해봤다.

const solution = (s) => {
  let count = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] == "(") {
      count++;
    } else {
      if (count == 0) {
        return false;
      }
      count--;
    }
  }
  if (count != 0) {
    return false;
  }
  return true;
};

• 분명 for문에서 s.length이런 식으로 작성하면 매번 length를 계산해야 돼서 느려진다고 들었는데 오히려 변수 선언해서 length를 담아두는 방식이 실행 시간은 더 오래 걸렸다.
  (할당에 시간이 그렇게 오래 걸리나?)

• 그리고 스택에 push하고 pop하는 것도 분명 시간복잡도가 1인 걸로 알고 있는데 스택을 사용하는 것보다 count로 숫자 연산하는 편이 시간이 덜 걸렸다.
  (그럼 배열을 할당하는데 시간이 걸린 걸까?)