[Python] 백준 9012 괄호

 

 

문제 분석

• VPS인가 아닌가
• VPS란 : 한 쌍의 괄호 기호로 된 문자열인가? 즉, '('가 나오고 ')'가 나왔는가
• 최종 출력은 VPS면 "YES" 아니면 "NO"

 

코드 설계

• T : 이후 몇 번의 VPS인지를 검사할 것인가
• T번 반복하여 
• 입력을 list에 받아 list 길이만큼 반복
• '('가 나오면 +1 , ')'가 나오면 -1
• 0이면 "yes" 아니면 "no"

 

• 괄호 문자열의 길이는 2 이상 50 이하이다. 관련하여 시간 복잡도 ??
• 입력을 list에 받을때 띄어쓰기가 안되어있어서 input().split()으로 하면 1개의 원소로 들어간다. 

 

• 아니다. 그냥 문자열로 받아서 문자열에 대한 반복문으로 해서 요소 하나씩 검사

 

정답 코드

1차 - 틀림

import sys
input = sys.stdin.readline

t = int(input())
cnt = 0

for _ in range(t):
    s = input()
    for i in s:
        if s == '(' :
            cnt += 1
        elif s == ')' :
            cnt -= 1
    if cnt == 0 :
        print('YES')
    else :
        print('NO')

• 다 YES라고 대답..
• 그리고 갯수를 세지말고 stack을 활용하자..
• 그리고 괄호가 열리고 나서 닫혀야 VPS이다. 따라서 먼저 열렸는지를 체크하는 조건이 필요
• 이렇게 할거면 cnt가 음수가 되지 않도록 조건을 만들워줘야함
• 왜 안되는거지..?

 

2차 

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    s = input()
    stack = []

    for i in s:
        if i == "(" :
            stack.append(i)
        elif i == ")" :
            if stack : # stack이 비어있지 않다면
                if stack[-1] == "(":
                    stack.pop()
                else :
                    stack.append(i)
            else : # stack이 비어있다면
                stack.append(i)

    if not stack :
        print('YES')
    else :
        print('NO')