[Python] 백준 9012번 : 괄호

 

접근 방법 1 - 괄호 개수를 count하여 비교

이 문제의 조건을 구현하기 위해 아래의 두 가지 조건을 충족해야 한다.

 

1. 괄호를 더하는 과정에서 어느 순간에도 )가 (보다 많아지면 안된다.

2. (와 )의 개수는 서로 같아야 한다.

 

이를 위해 (와 )의 개수를 각각 left, right로 두고 코드를 구현하였다.

import sys

T = int(input())

candidates = []

for _ in range(T):
    candidate = sys.stdin.readline().strip()
    candidates.append(candidate)

for letter in candidates:
    left = 0
    right = 0

    for l in letter:

        if right > left:
            break

        if l == "(":
            left += 1
        elif l == ")":
            right += 1

    if right == left:
        print("YES")
    else:
        print("NO")

 

 

접근 방법 2 - Stack

왼쪽에서 오른쪽으로 순서대로 확인하면서 Stack을 사용한다.

 

1. stack에는 (만 push로 들어간다.

2. )이 나오면 pop을 통해 stack에서 꺼낸다.

3. 만일 pop을 했는데 stack이 비어있으면, 즉 짝이 없으면 VPS가 아니다.

4. 문자열을 전부 확인했는데 stack에 남은 괄호가 있으면 VPS가 아니다.

 

import sys

T = int(input())

for _ in range(T):
    string = sys.stdin.readline().strip()
    stack = []
    is_vps = True

    for s in string:
        if s == "(":
            stack.append(s)
        elif s == ")":
            if not stack:
                is_vps = False
                break
            stack.pop()

    if stack:
        is_vps = False

    if is_vps:
        print("YES")
    else:
        print("NO")