[Python/코테] 백준 9012 괄호

9012 괄호

문제 및 조건 설명: https://www.acmicpc.net/problem/9012

알고리즘 설계

💡idea.

• 올바른 VPS 즉 한 쌍을 이루는 "()"이 되기 위해서는 ")"이 "("보다 먼저 나와서는 안된다. 
• 닫는 괄호가 나왔을 때 그 앞에서 여는 괄호가 있어야 하면 되므로 빠른 탐색과 쌍을 이룬 뒤 원소 제거를 위해 stack 자료구조를 사용한다.

🎲step.

1. 입력받은 문자열 중, 여는 괄호면 stack에 push한다.
2. 닫는 괄호면 stack의 마지막 원소가 여는 괄호 "("였는지 확인한다.
   1. 아니면 이 문자열은 VPS가 아니다. "NO"를 출력한다.
   2. 맞으면 VPS 쌍을 이뤘으므로, 방금 확인한 "("를 stack에서 pop한다.
3. 1번과 2번을 반복한다.
4. 문자열을 끝까지 탐색했을 때, stack에 아무것도 남아있지 않으면 모두 짝을 이루었다는 뜻으로 "YES"를 출력한다.
5. 아니면 "NO"를 출력한다.

알고리즘 구현

import sys
from collections import deque

n = int(input())

for _ in range(n):
    input = list(sys.stdin.readline().strip())
    stack = deque()
    isVPS = True

    for item in input:
        if item == '(':
            stack.append(item)

        elif item == ')':
            if len(stack) == 0:
                isVPS = False
                break
            else:
                if stack[-1] == '(':
                    stack.pop()
                else:
                    isVPS = False
                    break

    if len(stack) == 0 and isVPS:
        print("YES")
    else:
        print("NO")

나다어

• 인덱스 사용 시, 배열이 비어 있지 않은지를 먼저 검사해주기.
• 스택을 구현하기 위해서도 deque를 사용한다.