[맛있는물회] <SWEA알고리즘> 4866번 "괄호검사 "

문제 조건

---

주어진 입력에서 괄호 {}, ()가 제대로 짝을 이뤘는지 검사하는 프로그램을 만드시오.

예를 들어 {( )}는 제대로 된 짝이지만, {( })는 제대로 된 짝이 아니다. 입력은 한 줄의 파이썬 코드일수도 있고, 괄호만 주어질 수도 있다.
 

정상적으로 짝을 이룬 경우 1, 그렇지 않으면 0을 출력한다.
 

print(‘{‘) 같은 경우는 입력으로 주어지지 않으므로 고려하지 않아도 된다.

 

Input

---

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50

다음 줄부터 테스트 케이스 별로 온전한 형태이거나 괄호만 남긴 한 줄의 코드가 주어진다.

 

Output

---

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

 

생각한 아이디어

---

전형적인 스택을 이용한 알고리즘 문제이다.

String 을 입력받고 하나씩 분석을 한다.

만약 입력값이 ( 나 { 이라면 스택에 push를 한다.

만약 입력값이 ) 나 } 이라면 스택에서 pop을 한 후 쌍을 비교한다

쌍이 맞지않다면 에러, 스택이 비어있는데 pop을 하려한다면 에러

 

소스코드

T = int(input())

for TC in range(1, T + 1):
    stk = []
    ans = 1
    String = str(input())
    strArr = list(String)
    for i in range(0, len(strArr)):
        if strArr[i] == '(' or strArr[i] == '{':
            stk.append(strArr[i])
        elif strArr[i] == ')' or strArr[i] == '}':
            if not stk:
                ans = 0
                break
            P = stk.pop()
            if strArr[i] == ')' and P != '(':
                ans = 0
            elif strArr[i] == '}' and P != '{':
                ans = 0
    if stk:
        ans = 0
    print("#%d %d" %(TC, ans))

 

*파이썬 문법 정리

- C++와 같이 파이썬도 스택이 있는 줄 알았는데 따로 있지는 않고 List를 사용하여 append와 pop을 사용한다.

- 리스트가 비어있는지 확인하는 방법은 len(list) 로 할 수도 있고,

if list : 로 진행하면 list 안에 값이 있다면 이라는 뜻이다.

- 이 문제에서 스트링 분석이 끝이났는데 stack에 값이 남아있거나 stack에 값이 없는데 pop하려한다면 오류가 발생한다.