[SWEA][stack] 4866_괄호검사 (211019)

이해도

★★★★★

문제

접근방법

• stack 이 빌 때까지 반복하며 여러 경우의 수를 처리한다.
• 스택이 다 비면 1, 그렇지 않으면 0, 중간에 여러 경우의 수에 걸리면 0을 출력한다.
• left 리스트의 인덱스와 right 리스트의 인덱스가 일치하면 짝이 맞는 괄호이다.

[경우의 수]

1. 스택은 비어있는데 우측 괄호가 나온 경우 ex. ) or }

2. 스택의 마지막 괄호와 다음 괄호의 인덱스가 다른 경우 ex. ({)

3. data를 다 돌았는데 stack이 남아있는 경우 ex. ) , } , )} , { ,...etc

 

나의 코드

• while 반복문 사용
• left, right 분리

T = int(input())
for tc in range(1, T+1):
    data = list(input())

    left = ['{', '(']
    right = ['}', ')']

    stack = [0]
    ans = 1
    while stack:
        stack = []
        for char in data:
            if (len(stack) == 0) and (char in right):
                ans = 0
                break
            if char in left:
                stack.append(char)
            if char in right:
                if left.index(stack[-1]) == right.index(char):
                    stack.pop()
                else:
                    ans = 0
                    break
        if stack:
            ans = 0
            break

    print(f"#{tc} {ans}")

 

for 반복문을 사용한 코드

좌측 괄호가 나온 경우에는 항상 append하고, 우측 괄호로 모든 경우의 수를 처리한다.

다음의 경우 False를 반환한다.

• 우측 괄호를 만났는데 스택이 비어있는 경우
• 우측 괄호를 만났는데 스택 마지막 괄호와 인덱스가 다른 경우
• 다 돌았는데 스택이 남아있는 경우

def is_matched(text):
    lefty = '({'
    righty = ')}'

    stack = []
    for char in text:             
        if char in lefty:
            stack.append(char)
        elif char in righty:
            # isEmpty
            if len(stack) == 0:
                return False
            if righty.index(char) != lefty.index(stack[-1]):
                return False
            if righty.index(char) == lefty.index(stack[-1]):
                stack.pop()
    if len(stack):
        return False
    else:
        return True
    
    
T = int(input())
for tc in range(1, T+1):
    text = list(input())
    
    print(f"#{tc} {int(is_matched(text))}")