본문 바로가기

알고리즘/알고리즘 문제

[python] 백준 > 괄호

[문제]

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

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

 

 

[나의 풀이]

import sys

n = int(sys.stdin.readline())
result = []
r = ''
for i in range(n):
    stack = list(sys.stdin.readline().rstrip())
    sum = 0
    for target in stack:
        if target == '(':
            sum += 1
        elif target == ')':
            sum -= 1
        if sum < 0:
            answer = 'NO'
            break
    if sum == 0:
        answer = 'YES'
    else:
        answer = 'NO'
    result.append(answer)

print('\n'.join(result))

 

[다른 사람의 풀이]

import sys
input = sys.stdin.readline
T = int(input())
def sol(p):
    stack = []
    for k in p:
        if k == '(':
            stack.append(k)
        else:
            if not stack:
                return 'NO'
            t = stack.pop()
            if t==')':
                return 'NO'
    if stack:
        return 'NO'
    return 'YES'
for _ in range(T):
    p = input().strip()
    print(sol(p))

 

from sys import stdin
input = stdin.readline
T = int(input())
VPS_list = [input().split() for _ in range(T)]
for i in VPS_list:
    YorN = True
    r = 0
    l = 0
    if i[0].count('(') == i[0].count(')'):
        for j in i[0]:
            if j == "(":
                l += 1
            else:
                r += 1
            if r > l:
                print("NO")
                YorN = False
                break
        if YorN:
            print("YES")
    else:
        print("NO")

 

num = int(input())

for i in range(num):
   vps = list(input())
   while len(vps) != 0:
      if vps[0] == ')':
         print('NO')
         break
      else:
         if ')' in vps:
            vps.remove(')')
            vps.remove('(')
         else:
            print('NO')
            break
   if len(vps) == 0:
      print('YES')