[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 올바른 괄호

문제 및 제한사항

 

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

- "()()" 또는 "(())()" 는 올바른 괄호입니다.

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

 

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

 

**제한사항**

문자열 s의 길이 : 100,000 이하의 자연수

문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

풀이 방법

 

1. 실패했던 스택 형태로 설명해보겠다.

스택은 후입선출의 방식으로 데이터를 저장 및 관리한다. 책상 위에 책을 올릴 때 맨 위에 올린 책부터 빼는 모양새다.

배열에 데이터를 추가할 때 push로 데이터를 추가한다. 그럼 1, 2, 3, 4 중 4가 가장 늦게 들어왔으나 pop을 사용해 4부터 지워준다.

이런 식의 자료구조가 스택인데, 이 문제는 스택/큐 형태로 풀어야 할 것 같았으나 그렇게 하니 유효성에서 빠꾸가 났다.

 

아무튼 stack이라는 빈 배열을 선언한 후, 문자열 s를 for문으로 순회한다. 만약 s[i]가 '('라면 stack에 push한다.

'('가 아닐 때에, 즉 ')'일 때는 2가지 경우가 있다.

1) stack의 길이가 0인지 ==> '('가 없는 상태에서 지금 ')'를 만난 거다. ==> false

2) stack.pop() ==> stack에 '('가 있으므로 ')'를 만나 지워준다.

 

이 구조를 반복하며 for문의 바깥에는 그래서 stack의 길이가 0인지를 확인한다.

정상적인 () 의 형태로 잘 열리고 닫혔다면 모두 pop되어 stack이 비어 있을 것이기 때문이다.

 

그런데 이 구조로 문제를 풀면 유효성에서 오류가 난다.

왜냐하면 문자열이 길 때, 일일이 push pop을 반복하기 때문이다.

 

2. 그렇다면...

배열로 반복하지 말고 숫자로 풀어보았다.

1번과 동일한데, count = 0 으로 선언한 후 '('라면 1을 더해주고 ')'라면 1을 빼 정상적인 ()의 형태일 때 0인지 확인하면 된다.

대신 여기선 stack의 길이가 0인지 확인할 수 있는 방법을 count가 음수인지로 바꿨다.

만약 '('보다 ')'가 많으면 뺄셈이 더 많아져서 음수가 되기 때문이다.

 

스택과 큐를 공부해볼 수 있었던 문제였다.

 

코드

function solution(s) {
  let count = 0;
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (char === '(') {
      count++;
    } else {
      count--;
    }
    if (count < 0) {
      return false;
    }
  }
  return count === 0;
}