백준 9012번 괄호문제 - Python

문제

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

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

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입력 1 

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1

NO
NO
YES
NO
YES
NO

예제 입력 2

3
((
))
())(()

예제 출력 2

NO
NO
NO

이 문제는 설명이 개인적으로 이해하기 어려웠습니다  쉽게 설명해보자면...  열린 괄호 '(' 를 닫는 괄호 ')' 와 한 쌍을 만들어주도록 하였을 때 홀로 존재하는 '(' or ')'가 존재하면 틀린 것이며 또한 (로 열고 )로 닫는 순서를 지켜야함을 요구하고 있습니다

즉, 괄호( '('  or ')' )가 홀로 존재하는 것이 없는지 확인해서 홀로 존재하는 게 있으면 NO, 홀로 존재하는 것이 없고 순서도 '(' ')'로 다 쌍이 맞으면 YES를 출력하라는 뜻 입니다 

이런 유형의 문제들은 대부분 스택을 사용합니다. 스택은 자료구조로서 우리가 흔히 사용하는 리스트의 종류로는 순차형 리스트, 연결리스트 등이 있지만 위 문제를 푸는데 가장 쉬운 리스트는 순차형리스트 그 중에 대부분 언어에서 기본적으로 구현되어 있는 배열을 사용하도록 하겠습니다

스택은 리스트를 LIFO(Last Input First Out)구조로 표현하는 것 입니다 

가장 마지막에 넣은 것이 나올때는 먼저 나오는 구조 입니다. 파이썬에서는 append()로 리스트의 맨 마지막에 집어넣을 수 있으며 pop()로 맨 마지막 요소를 뺄 수 있습니다. 이것을 활용하여 문제를 해결 할 수 있습니다

이 문제는 입력값이 많기 때문에 input()이 아니라 sys.stdin.readline()을 사용했습니다

#9012번 실버4 괄호문제
import sys


def YesorNo(problem):
    stack = []
    if problem[0] == ')': # ')'로 시작은 (로 시작해서 )로 덮는 한 쌍의 규칙을 불충족
        return 'NO'
    else:
        stack.append(problem[0])
    for i in range(1, len(problem)): # [1] 인덱스부터 순회
        if problem[i] == '(':  # 입력 받은 값은 '('인경우
            stack.append(i)
        else:  # 입력 받은 것은 ')'인경우
            if len(stack) > 0:  # 스택에 '('가 남아있는 경우
                stack.pop()
            else:  # 스택이 비어있는 경우
                return 'NO'

    if len(stack) == 0:  # 모든 값을 다 순회, 스택에서 '('도 다 비워져있는 경우
        return 'YES'
    else:  # 스택에 '('가 남아있는 경우
        return 'NO'
        
        
N = int(input())
problemList = []
for _ in range(N):
    tmp = sys.stdin.readline().strip()
    problemList.append((list(tmp)))

for i in range(N):
    print(YesorNo(problemList[i]))

이 문제를 해결하는데 해당 기능을 별도의 함수 YesorNo 로 표현하여 재사용성을 높여서 해결하였습니다