[BOJ] 9012. 괄호

Python3

문제

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

입출력

입출력 예시

키워드

• 스택

문제 풀이

(23.5.3 추가)

문제 요구사항

• 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다.
• 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

변수 및 함수 설명

• t: 테스트 케이스 개수
• ps: 괄호 문자열 리스트 (문자열 길이는 2 이상 50 이하)
• vps: 한 쌍의 괄호인지 판단하는 변수
• st: 괄호를 저장하는 스택

풀이

여는 괄호는 +1로, 닫는 괄호는 -1로 나타내고 둘의 최종합이 0이 되면 vps이다.

(입력 및 선언)

• 테스트케이스 개수를 입력 받는다.

(반복문)

• 괄호를 문자열로 입력 받고 리스트에 넣어준다.
• 이를 담는 변수 vps는 반복문 안에서 0으로 초기화시킨다.

• 문자열 한 줄씩 vps인지 판단해야 한다.
• '(' 는 1씩 증가시키고, ')'는 1씩 감소한다.
• 이때 만약 vps가 음수(-1)이라면 ')'로 시작한 것이므로 vps가 될 수 없다.
  => NO를 출력하고 반복문 break.

• vps가 0이라면 YES를 출력하고, vps가 0보다 크면 NO를 출력한다.

---

스택으로 풀이
(23.5.4 추가)

• 여는 괄호 '('일 때 스택(st)에 추가
• 닫는 괄호 ')'일 때는 두 가지 경우로 나누기
• • 스택(st)에 들어 있으면 pop해서 삭제
  • 비어 있으면 닫는 괄호부터 시작하는 것이므로, NO 출력하고 break
• break를 거치지 않고,
• • 스택에 아무것도 들어 있지 않으면 YES 출력
  • 아니면 NO 출력

최종 코드

• 스택

t = int(input())

for _ in range(t):
    s = list(input())
    st = []
    
    for i in s:
        if i == '(':
            st.append('(')
        elif i == ')':
            if st:
                st.pop()
            else:
                print('NO')
                break
    else:       
        if len(st) == 0:
            print('YES')
        else:
            print('NO')

• 변수를 사용한 풀이

import sys
t = int(sys.stdin.readline())

for i in range(t):
    p = input()
    ans = list(p)
    vps = 0

    for i in ans:
        if i == '(':
            vps += 1
        elif i == ')':
            vps -= 1
        if vps < 0:
            print('NO')
            break
        
    if vps > 0:
        print('NO')
    elif vps == 0:
        print('YES')

t = int(input())

for _ in range(t):
    ps = list(input())
    
    vps = 0
    
    for i in ps:
        if i == '(':
            vps += 1
        elif i == ')':
            vps -= 1
        if vps < 0:
            print('NO')
            break
            
    if vps == 0:
        print('YES')
    elif vps > 0:
        print('NO')