[백준] 9012번: 괄호

[백준] 9012번: 괄호

[링크]

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

 

 

[문제]

 

 

[풀이]

핵심

• 올바른 괄호 문자열은 '('(여는 괄호)와 ')'(닫는 괄호) 개수가 같아야 한다.
• 여기서 순서가 중요한데 개수만 같아서 올바른 괄호 문자열이 되는 건 아니다.

 

1. VPS함수는 올바른 괄호 문자열이면 True, 아니면 False를 반환한다.

2. right변수는 닫는 괄호의 개수를 카운트 한다.

3. 문자열의 오른쪽부터 순서대로 순회를 한다.

4. 닫는 괄호는 right +=1, 여는 괄호는 right-=1

5. 이때 right가 음수가 된다면, 여는 괄호가 닫는 괄호 없이 먼저 나왔다는 의미이므로

   더 이상은 올바른 괄호 문자열이 될 수 없어 False 반환 한다.

6. 모든 문자열을 다 순회 하고 right가 0이라면 여는 괄호와 닫는 괄호가 짝이 맞는다는 의미이므로 True반환.

 

 

[코드]

# 9012번(괄호)
def VPS(vps_str):
    #들어온 문자열을 list로 만든다.
    vps_list=list(vps_str)
    #닫는 괄호 개수 카운트
    right=0
    while vps_list:
        #비교 문자열
        comp=vps_list.pop()
        if comp == '(':
            right-=1
        else:
            right+=1
        #닫는 괄호의 개수가 음수가 되면 바로 False 리턴.
        if right<0: return False
 
    return True if right==0 else False
 
N=int(input())
for _ in range(N):
    vps_str=input()
    print('YES' if VPS(vps_str) else 'NO')