[백준] 9012 : 괄호 (Python/파이썬)

문제 링크

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

문제

괄호 문자열(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”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제

입력

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

출력

NO
NO
YES
NO
YES
NO

---

정답 및 풀이

import sys

input = sys.stdin.readline

def is_correct_parenthesis(string):
    stack = []
    for i in range(len(string)):
        if string[i] == '(':
            stack.append('(')
        else:
            if len(stack) == 0:
                return False
            else:
                stack.pop()
    if len(stack) == 0:
        return True
    else:
        return False

n = int(input().strip())
for i in range(n):
    ps = input().strip()
    if is_correct_parenthesis(ps):
        print("YES")
    else:
        print("NO")

1. import sys
   • 빠른 입력을 위해 sys 모듈을 불러온다.
2. input = sys.stdin.readline
   • input() 대신 더 빠른 입력 방식을 사용하도록 설정한다.
3. def is_correct_parenthesis(string):
   • 괄호 문자열이 올바른지 판단하는 함수를 정의한다.
4. stack = []
   • 여는 괄호 '(' 를 저장할 스택 리스트를 초기화한다.
5. for i in range(len(string)):
   • 문자열의 각 문자를 순서대로 확인하기 위해 반복을 시작한다.
6. if string[i] == '(':
   • 현재 문자가 여는 괄호 '('라면
7. stack.append('(')
   • 스택에 '(' 를 push한다.
8. else:
   • 현재 문자가 닫는 괄호 ')'라면
9. if len(stack) == 0:
   • 스택이 비어 있다면 매칭될 여는 괄호가 없기 때문에 올바른 괄호가 아니다.
10. return False
    • 올바른 괄호 문자열이 아니므로 즉시 False를 반환한다.
11. stack.pop()
    • 스택에 '('가 있으면 pop하여 짝을 맞춘다.
12. if len(stack) == 0:
    • 모든 문자를 처리한 뒤 스택이 비어 있으면
    • 여는 괄호와 닫는 괄호가 정확히 짝을 이룬 것이다.
13. return True
    • 올바른 괄호 문자열임을 반환한다.
14. else:
    • 스택에 여전히 '('가 남아 있는 경우
15. return False
    • 닫는 괄호가 부족해 짝이 맞지 않으므로 False를 반환한다.
16. n = int(input().strip())
    • 테스트 케이스 개수 n을 입력받는다.
17. for i in range(n):
    • 괄호 문자열을 n번 검사하기 위한 반복문이다.
18. ps = input().strip()
    • 검사할 괄호 문자열을 입력받는다.
19. if is_correct_parenthesis(ps):
    • 정의해둔 함수로 괄호 문자열이 올바른지 확인한다.
20. print("YES")
    • 올바른 괄호 문자열(VPS)이면 YES를 출력한다.
21. print("NO")
    • 올바르지 않으면 NO를 출력한다.

---