[JavaScript/코딩테스트] <백준 - 9012번 괄호>

http://(https://www.acmicpc.net/problem/9012

 

예제 입력

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

 

예제 출력

NO
NO
YES
NO
YES
NO

 

 

풀이

 

문제 자체는 어렵지 않다

열린 괄호 '(' 와 닫힌 괄호 ')'  가 정상적으로 배치되어  올바른 괄호인지 확인하는 문제이다.

 

---

틀린 정답

 

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

let N = Number(input[0]);
let result = [];

for (let i = 1; i <= N; i++) {
  if (input[i].length % 2 !== 0) {
    result.push('NO');
  } else {
    const X = input[i].split('');

    let mid = input[i].length / 2;
    let left = X.slice(0, mid);
    let right = X.slice(mid);

    // right 배열을 복사하여 뒤집고, left와 비교
    if (JSON.stringify(left) === JSON.stringify(right.slice().reverse())) {
      result.push('YES');
    } else {
      result.push('NO');
    }
  }
}

console.log(result.join('\n'));

 

나는 문제를 보면 자료 구조 '스택'에 관한 문제이기 때문에

데칼코마니처럼 배열의 길이를 반으로 각각 나눠

왼쪽과 오른쪽 값이 같으면 정답인줄 알았다

하지만

(()())((()))

이거와 같이 [(()))] [((()))] 왼쪽과 오른쪽으로 나눴을 때

내 코드 기준에선 올바른 괄호가 아니지만 실제론 올바른 괄호였다.... 

 

---

 

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

const N = Number(input[0])
let result = []; //최종 정답

for(let i =1; i <= N; i++){
    let tmp = []; //스택으로 사용할 용도
    let fact = true;
    
    for(const x of input[i]){
        
        // case 1
        if(x == '('){
            tmp.push(x)
        }
        //  case 2
        else{
            // case 2.1
            if(tmp.length == 0){
               fact = false
                break
               }
                case 2.2
               tmp.pop()
        }
    }   
        if(fact && tmp.length == 0){
            result.push("YES")
        }else{
            result.push("NO")
        }
    }

console.log(result.join('\n'))

 

이거 역시 '스택'을 사용한 풀이지만  

위에 코드와는 다르게 올바른 괄호인지 확인 할 수 있다.

 

'(' 이거 일 때 스택에 넣고 아닐 때 빼는 코드이다.

fact 변수를 통해 괄호가 올바른지 아닌지 구별했다

위의 이미지는 마지막 스택에 tmp는 비어있지만 fact 가 false이기 때문에 "NO"를 출력한다.