[알고리즘][Python] 백준(BOJ) 9012 괄호_파이썬

 

9012 괄호    www.acmicpc.net/problem/9012

9012번: 괄호

 

 

문제 풀기 전 공부할 것 : 자료 구조, 문자열, 스택

 

 

 

 

 

 

 

풀이 1

<내용>

• vps를 확인하는 check 함수를 만든다.
• cnt를 0으로 초기화한다.
• 그리고 vps에서 괄호를 하나씩 꺼낸다.
• 꺼낸 괄호가 ')' 모양이라면 cnt에 더하기 1을 한다.
• 꺼낸 괄호가 '(' 모양이라면
  • cnt가 0보다 작거나 같으면 올바른 괄호가 아니다.
  • cnt가 0보다 클 때 cnt에 빼기 1을 한다.
• vps가 비었을 때
  • cnt를 확인하고 0이 아닌 경우 올바른 괄호가 아니다.

 

 

<코드>

import sys
input = sys.stdin.readline

t = int(input())

def check(vps):
    cnt = 0
    while vps:
        v = vps.pop()
        if v == ')':
            cnt += 1
        else:
            if cnt <= 0:
                return False
            cnt -= 1
    if cnt != 0:
        return False
    return True

for _ in range(t):
    vps = list(input().rstrip())
    if check(vps):
        print('YES')
    else:
        print('NO')

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 위의 방법과 동일하게 진행된다.
• 여기서는 cnt가 아닌 stk(stack)의 형태로 올바른 괄호를 확인한다.
• stk를 [](빈 리스트)로 초기화한다.
• 그리고 vps에서 괄호를 하나씩 꺼낸다.
• 꺼낸 괄호가 ')' 모양이라면 stk에 추가한다.
• 꺼낸 괄호가 '(' 모양이라면
  • stk가 비었다면 올바른 괄호가 아니다.
  • stk가 비어있지 않을 때 stk에 pop을 한다.
• vps가 비었을 때
  • stk를 확인하고 비어있지 않은 경우 올바른 괄호가 아니다.

 

 

<코드>

import sys
input = sys.stdin.readline

t = int(input())

def check(vps):
    stk = []
    while vps:
        v = vps.pop()
        if v == ')':
            stk.append(v)
        else:
            if not stk:
                return False
            stk.pop()
    if stk:
        return False
    return True

for _ in range(t):
    vps = list(input().rstrip())
    if check(vps):
        print('YES')
    else:
        print('NO')