[프로그래머스 Lv2] 올바른 괄호

올바른 괄호

문제

괄호가 바르게 짝지어졌다는 것은 ( 문자로 열렸으면 반드시 짝지어서 ) 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• ()() 또는 (())() 는 올바른 괄호입니다.
• )()( 또는 (()( 는 올바르지 않은 괄호입니다.

( 또는 ) 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한 사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 ( 또는 ) 로만 이루어져 있습니다.

---

코드

1. 정규표현식 이용 - 시간 초과

function solution(s){
  // early return을 위한 예외처리
  if (s.length % 2 !== 0 || s.startsWith(')') || s.endsWith('(')) {
    return false;
  }
  if (s.match(/\(/g).length !== s.match(/\)/g).length) {
    return false;
  }
  
  let brackets = s;
  let length = s.length;
  while(brackets) {
    brackets = brackets.replaceAll(/\(\)/g, '');
    // 이전 길이와 같으면 false
    if (length === brackets.length) {
      return false
    }
    // 다 사라지면 true
    if (brackets.length === 0) {
      return true;
    }
    length = brackets.length;
  }
}

while문 내에서 정규표현식을 이용해 ()를 빈 문자열로 치환하는 과정을 반복한다.

이전 길이와 같으면 (더이상 치환될 괄호가 없으면) false, 길이가 0이 되면 true를 반환한다.

그러나 시간 초과로 실패..

---

2. 괄호 개수를 비교하는 방법

function solution(s){
  let cnt = 0;
  
  for (let i=0; i<s.length; i++) {
    // (이면 +1, )이면 -1
    cnt += (s[i] === '(' ? 1 : -1);
    
    // cnt가 마이너스가 되면 )가 더 많다는 뜻이므로 실패.
    if (cnt < 0) return false;
  }
  return (cnt === 0 ? true : false);
}

결국 힌트를 얻어 풀었다. 이렇게 간단하게 생각할 수 있다니..!

index 0부터 괄호를 돌아가면서, 여는 괄호 (이면 +1, 닫는 괄호 )이면 -1을 더한다.

cnt가 마이너스가 되면 )가 더 많아진다는 뜻이므로, 이때부터는 어떤짓을 해도 괄호를 닫을 수 없게 된다. 따라서 false를 반환한다.

반복문이 끝난 후 cnt가 0이 되면 true, 아니면 false를 반환한다.

---

알게 된 것

처음에는 for…of 문을 사용했는데, 이상하게 같은 코드를 써도 효율성에서 실패할 때도 있고, 성공할 때도 있었다.

for문의 성능 문제인가 싶어 기본 for문으로 바꾸어 실행해보니 시간초과가 발생하지 않았다.

찾아보니 for > for…of > forEach 순으로 실행 속도가 빠르다고 한다.
About JavaScript Loop Performance(forEach, for, while, etc...)

---

💡 결론

성능을 고려한다면 기본 for문을 사용하도록 하자.