BOJ 9012 괄호

https://www.acmicpc.net/problem/9012
시간 2초, 메모리 128MB
input :

• 정수 T
• 괄호 문자열(2 <= 문자열 <= 50)

output :

• 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”

조건 :

• “( ( ) ) ( )”와 “( ( ( ) ) )” 는 VPS
• “( ( ) (”, “( ( ) ) ( ) ) )” , 그리고 “( ( )” 는 모두 VPS 가 아닌 문자열

---

우린 left를 이용해서 이 문자열이 쌍을 이루는지 확인 할 수 있다.
"("이 나오면 left += 1
")"이 나오면 left -= 1 을 해서 계산을 하는데.

left가 음수가 되는 부분이 생기면 쌍을 못 이루는 것이기에 break를 걸고 flag를 반전시킨다.
또는 left만 나올 경우인데, 다시 보면 left가 마지막까지 수행되고 0이 되지 못하는 경우는 언제나 쌍을 이루지 못하는 것이다.
그래서 flag, left 개수를 이용해서 출력을 하자.

import sys

n = int(sys.stdin.readline())

for i in range(n):
    string = sys.stdin.readline().strip()
    left = 0
    right = 0
    flag = 1
    for item in string:
        if item == '(':
            left += 1
        else:
            left -= 1
            if left < 0:
                flag = 0
                break

    if flag:
        if left != 0:
            print("NO")
        else:
            print("YES")
    else:
        print("NO")