9012 괄호

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

T = int(read())
result_array = []
for i in range(T):

    # '\n' 벗기는 작업
    temp = read().split()
    temp = temp[0]
    state = 0
    for idx,j in enumerate(temp) :
        if j == '(' :
            state += 1
        elif j == ')' :
            state -= 1
        # state가 -1이 나오는 순간 이 문자열은 VPS가 아니다.
        if state < 0 and idx <= len(temp):
            result_array.append('NO')
            break
        elif state == 0 and idx == len(temp) -1 :
            # 끝나는 순간 state 가 0 이면 이것은 VPS다
            result_array.append('YES')
        elif state > 0 and idx == len(temp) - 1:
            result_array.append('NO')
for k in range(T):
    print(result_array[k])

3. 생각 및 풀이

생각

이 문제는 아이디어가 중요한 문제였다.

문제 풀이

이 문제의 핵심 아이디어는 “VPS를 어떻게 판단할 것인가” 이다. 푸는 방법은 간단하다. state라는 변수를 만들어서 (가 나오면 +1을, )가 나오면 -1을 더해준다. 결국 VPS란 괄호()가 서로 열리고 닫히고를 반복하는 것인데, state가 0으로 시작해서 0으로 끝나지 않으면 괄호가 한번이라도 닫히지 않은 적이 있는 것이고, 음수가 나올경우엔 )가 (보다 더 많이 나왔다는 것을 의미한다.

이것을 말그대로 구현하면 끝나는 문제이다.