알고리즘 기초 1/2. 200 - 자료구조 1
9012번. 괄호

문제

9012번 문제 링크

solution

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const iter = input.shift();

for(let i = 0; i < iter; i++) {
  let parenthesis = input[i];
  
  let stack =  [];
  
  let result = 'YES';

  for(let j = 0; j < parenthesis.length; j++) {
    // "(" 문자가 입력된다면 stack에 1을 넣음.
    if (parenthesis[j] === '(') {
      stack.push(1);
    } else {
      // 만약, stack에 값이 있으면 false가 되어, 조건문 통과
      // 만약, stack에 값이 없으면 pop이 undefined가 나온다.
      // !undefined === true
      // 이 경우 VPS가 아니므로 NO 출력
      if (!stack.pop()) {
        result = 'NO';
        break;
      } 
    }
  }

  // 만약 stack에 값이 남아있다면 VPS가 아니므로 NO 출력
  if (stack.length !== 0) {
    result = 'NO';
  }

  console.log(result);
}

이번 문제는 완전히 잘못 짚었다...그래서 다른 분 풀이를 찾아보다가 너무 이해가 잘되는 풀이가 있어서 가져와봤다.(참고 자료 1)
스택 구조를 이용하셨다. 왜 이 생각을 못했을까..

코드에 주석을 달아놓았지만, 역시나 예시로 보는게 더 이해가 빠르다.

우선 필자 생각으로는 완전히 NO가 되는 경우는 다음과 같다.
1. 문자열의 길이가 홀수인 경우.
"("가 나오면 ")"가 나와야만이 VPS이므로, 꼭 문자열의 길이가 짝수여야한다.

2. "("로 시작해야만한다.
만약 ")"로 시작하면 VPS가 되지않는다.

3. ")"로 끝나야만한다.
만약 "("로 끝나면 VPS가 되지않는다.

// YES인 경우
예시 1 : ()()()()(()()())()

"("가 나올 때마다 stack에 1이 push된다.

")"가 나오면 stack.pop을 통해 배열 맨 뒤의 1이 삭제된다.

그러면 예시 1의 경우는 다음과 같다.
push는 +1, pop은 -1로 표시했다.

+1 -1 +1 -1 +1 -1 +1 -1 +1 +1 -1 +1 -1 +1 -1 -1 +1 -1

총 합은 0이 된다. 따라서 YES.
각 단계에서의 총 합이 0 아래로 떨어지지 않는다는 점을 주목!
참고로 문자열의 길이는 짝수이다.

// NO인 경우
예시 2 : ())(()

+1 -1 -1 ...
2번째 부분에서 합이 0이 되어서 stack 배열이 비어있는 상태인데
3번째 부분에서 pop을 진행했으므로 result가 NO가 된다.
참고로 문자열의 길이는 짝수이다.

예시 3 : (())())
문자열의 길이가 홀수이다.

+1 +1 -1 -1 +1 -1 -1

마지막 단계에서 -1이 된다. 즉, 빈 배열에서 pop을 했으므로
NO가 출력된다.

예시 4: (()((())()(
문자열의 길이가 홀수이다.

+1 +1 -1 +1 +1 +1 -1 -1 +1 -1 +1

총 합이 4이다. 즉, stack 배열에 1이 4개 존재하고 있는 것이다.
stack.length가 0이 아니므로 NO가 출력된다.

참고 자료

참고 자료 1
참고 자료 2