[ Python Coding ] 백준 9012. 괄호

문제

입력 및 출력

시도

n = int(input())

for i in range(n):
    left = []
    right = []
    
    t = input()
    
    for j in range(len(t)):
        if t[j] == '(':
            left.append('left')
            
        elif t[j] == ')':
            right.append('right')
            
    if len(left) == len(right):
        print(len(left), len(right))
        print('YES')

    else:
        print(len(left), len(right))
        print('NO')

💡 Think
처음에 단순히 괄호의 개수를 세어 '( 개수와 ) 개수가 똑같으면 올바른 괄호 문자열이지 않을까?' 라는 생각이 들었다.

그러나, 예제 입력 2의 ())(()는 올바른 괄호가 아닌데 YES가 나왔다.
이때 '괄호의 개수가 같다고 해서 올바른 괄호라고 판단하면 안되겠구나'라는 것을 깨달았다.
그래서 수행하게 된 것이 다음 코드이다.

최종 실행 코드

a = int(input())

for i in range(a):
    b = input()
    sum = 0
    
    for i in b:
        if i == '(':
            sum += 1
            
        elif i == ')':
            sum -= 1
            
        if sum < 0:
            print('NO')
            break
            
    if sum > 0:
        print('NO')
        
    elif sum == 0:
        print('YES')

풀이

• 위의 시도와 비슷한 느낌이다.

• 올바른 괄호의 첫 시작은 무조건 (로 시작한다.

• 이를 활용하여 (가 등장하면 +1을 하고, )가 등장하면 -1을 한다.

• (는 아무리 많아도 상관 없지만, )가 먼저 시작되면 이는 올바른 괄호가 아니다.
  앞의 (보다 뒤의 )개수가 더 많아도 올바른 괄호가 아니다.

• 따라서 음수가 되는 경우에는 더이상 뒤의 문자열을 확인해보지 않고 break문을 걸어 NO를 출력하고, 바로 for문을 탈출한다.

• 합계 sum>0이면, (의 개수가 더 많다는 의미이므로 올바른 괄호가 아니다.

• 그리고 sum=0이면 올바른 괄호를 뜻하므로 YES를 출력한다.

[문제 링크]
https://www.acmicpc.net/problem/9012