SWEA 4866 괄호검사 (python)

4866. [파이썬 S/W 문제해결 기본] 4일차 - 괄호검사

 

파이썬 SW문제해결 기본 - Stack1

2021.06.05 - [Algorithm] - SWEA 4869 종이붙이기 (python)

2021.06.05 - [Algorithm] - SWEA 4866 괄호검사 (python)

2021.06.05 - [Algorithm] - SWEA 4871 그래프 경로 (python)

SWEA 4871 그래프 경로 (python)

2021.06.05 - [Algorithm] - SWEA 4873 반목문자 지우기 (python)

 

문제

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

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

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

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

 

[입력]

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

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

 

[출력]

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

 

코드

# 처음에는 딕셔너리로 접근했는데 시간이 훨씬 많이 걸리는듯
# 런타임 오류를 해결하기 위해서 직접 매칭으로 접근함
# 딕셔너리 참조가 많아질수록 기하급수적으로 늘어나는 듯?

T = int(input())

def check(line):
    # 스택 초기화
    stack = []
    # 길이만큼 반복하면서 확인
    for char in line:
        # 만약 열린괄호가 온다면 스택에 추가해줌
        if char == '(' or char == '{':
            stack.append(char)
        # 만약 닫힌 괄호가온다면
        elif char == ')' or char == '}':
            # 검사할 스택이 없다면 비어있는것!
            if not stack:
                return 0
            # 스택의 가장위가 가장 안의 괄호이기 때문에 팝으로 확인
            # pop을 비교문에만 써도 pop이 실행됨
            elif char == ')' and stack.pop() != '(':
                return 0
            elif char == '}' and stack.pop() != '{':
                return 0
    # 만약 여는 괄호가 남아있다면 no
    if stack:
        return 0
    return 1

for tc in range(1, T+1):
    line = list(input())
    print("#{} {}".format(tc, check(line)))