[백준] 9012 번 괄호

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

9012번: 괄호

문제를 간단히 요약해 보면 괄호기호로 구성되는 문자열을 PS(Parenthesis String)이라고 한다. 그중 올바른 괄호 문자열을 VPS(Valid PS)라고 부른다. 예를 들면 "((()))"는 VPS지만 "(()("같은 경우는 그냥 PS이다. 각 주어진 괄호 문자열이 VPS인지 판단해 결과를 YES 혹은 NO로 나타내어라

 

접근법 1

정석적인 스택 활용 풀이이다. 기본적인 접근법은 괄호는 "(" 와 ")"가 한 쌍이다. 스택에 들어가는 기준을 "(" 기호로 잡고, 문자열을 검색한다. 검색 조건은 아래와 같이 정리할 수 있다.

 

1. 만약 "("가 나온다면
   1. 스택에 "("를 push한다.
2. 만약 ")"가 나온다면
   1. 스택이 비어있는 경우에는 괄호 패턴("()")를 만족하지 않기 때문에 VPS가 아니다. 그러므로 NO를 반환한다.
   2. 스택이 비어있지 않는 경우에는 스택에서 "("를 pop합니다.
3. 모든 검사가 끝나고
   1. 스택이 비어있는 경우에는 VPS가 만족된 경우이므로 YES를 반환한다.
   2. 스택이 비어있지 않는 경우에는 VPS가 만족되지 않은 경우이므로 NO를 반환한다

구현 1

입력된 수만큼 반복문을 돌면서, PS를 받고, 검사하는 과정 방식으로 구현하였다.

import sys
from typing import MutableSequence

TRUE = "YES"
FALSE = "NO"

class VPS(object):
    def __init__(self):
        self.stack = []

    def setStack(self) -> None:
        self.stack = []

    def push(self, x : str) -> None:
        self.stack.append(x)
    
    def pop(self) -> None:
        self.stack.pop()
    
    def isEmpty(self):
        if not self.stack:
            return True
        else:
            return False
    def main(self,a : MutableSequence):
        self.setStack()
        #sys.stdin.readlin()은 마지막에 줄바꿈값 까지 문자열로 보기 때문에 -1번을 제외
        for i in a[:-1]:
            if i == "(":
                self.push(i)
            else:
                if self.isEmpty():
                    return FALSE
                else:
                    self.pop()
        if self.isEmpty():
            return TRUE
        else:
            return FALSE

if __name__ == "__main__":
    stk = VPS()  
    print(*[stk.main(sys.stdin.readline()) for _ in range(int(sys.stdin.readline()))],sep = "\n")

접근법2

접근법2는 재귀를 이용한 방법이다. 재귀적으로 순환하며 '()'를 기준으로 split을 하고 남은 문자열을 합쳐 다시 '()'로 split과정을 계속 하다 보면, VPS를 충족하는 PS인 경우에는 '빈 문자열' 값만 남게 됩니다. 만약 충족시키지 않는 경우에는 특정값이 남게 됩니다.

구현2

import re
import sys
from typing import MutableSequence
def VPSCheck(a : str):
    if len(a) == 1:
        if not a[0]:
            return "YES"
        else:
            return "NO"   
    return VPSCheck(''.join(a).split('()'))
    

if __name__ == "__main__":
    result = []
    for _ in range(int(sys.stdin.readline())):
        result.append(VPSCheck(sys.stdin.readline()[:-1].split('()')))
    print(*result,sep = "\n")