[알고리즘]백준 9012번: 괄호

import sys
from collections import deque 

N = int(sys.stdin.readline().strip())

for i in range(N):
    
    brakets = sys.stdin.readline().strip()
    brakets = deque([i for i in brakets])
    
    if len(brakets)%2!=0:
        print("NO")
    else: 
        cnt_bra =0 
        cnt_ket =0
        while brakets:
            if cnt_ket > cnt_bra:
                break
            else:
                braket= brakets.popleft()
                if braket=="(":
                    cnt_bra+=1
                else: 
                    cnt_ket+=1
        if cnt_bra == cnt_ket:
                
            print("YES")
        else: 
            print("NO")

괄호가 올바르게 구성되어 있는지 판단하는 문제 

 

3가지를 고려했는데 

 

1.괄호의 전체 갯수가 짝수인지

2. 괄호의 갯수가 (와 )가 같은지 

3.괄호의 순서가 맞는지 

 

알고리즘의 속도를 위해서 첫번째로 1번을 고려해주고 여기서 걸리면 반복문을 스탑한다

2과 3번은 괄호를 순서대로 빼주면서 (와 ) 의 갯수를 카운트해주면서 고려해주었다. 

 

괄호의 경우 )가 먼저 나오는 경우 (cnt_ket이 cnt_bra보다 큰 경우) 잘못된 경우이므로 

반복문을 스탑하고 NO를 출력한다 

 

마지막까지 반복했을때 둘의 갯수가 동일하면 YES를 출력한다