[알고리즘] 백준 9012 (파이썬 풀이)

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

9012번: 괄호

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

 

해결코드

t = int(input())
for i in range(t):
    n = input()
    li = list(n)
    cnt = 0
    for i in n:
        if(i=="("):
            cnt += 1
        elif(i==")"):
            cnt -= 1
        if(cnt == -1):
            print("NO")
            break
    if(cnt == 0):
        print("YES")
    elif(cnt > 0):
        print("NO")

 

문제풀이

 

일단 변수 t에 총 실행할 케이스 수를 입력한다.

t만큼 반복해야하기 때문에 for문을 입력한다.

n이라는 변수에 문자열을 받고 li라는 리스트에 n을 넣어 문자열을 쪼개 하나하나 인덱스에 넣는다.

실행 원리는 큐랑 마찬가지로 선입 선출을 이용한다.

'('가 들어오면 cnt값을 +1해주고, ')' 가 들어오면 cnt 값을 -1해준다.

입력받은 문자열이 찾고자하는 VPS문자열이라면 cnt값은 마지막에 0이 될것이다.

예외로는 '('가 들어오기 이전에 ')'가 먼저 들어오면 안된다.

만약 그럴경우(if cnt== -1)에는 바로 NO를 출력하고 break로 빠져나온다.

마지막에 cnt값이 0이면 YES를 출력하고 cnt값이 0보다 크다면 NO를 출력한다.