백준 9012(괄호) - 스택

https://www.acmicpc.net/problem/9012

 

 

일단 내가 생각한 풀이

 

• " (())()) "와 같은 문자열이 주어졌을 때, 여는 괄호 " ( "는 +1, 닫는 괄호 " ) "는 -1로 처리
• 다만, 예외적으로 "))(("와 같이 닫는 괄호가 여는 괄호보다 먼저 나오는 경우에도 합이 0이 될 수 있으므로, 합계가 0보다 작아지는 순간 루프를 즉시 종료하고valid = False로 설정.
• 루프가 끝난 후, valid가 True이면서 합계가 0이면 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력합니다.

 

❓ python 풀이

import sys

T = int(sys.stdin.readline().strip())  # 테스트 케이스 수
for i in range(T):
    l = sys.stdin.readline().strip()  # 각 괄호 문자열 입력 (개행 문자 제거)
    num = 0  # 괄호 균형을 나타내는 변수 초기화
    valid = True  # 올바른 괄호인지 확인하는 변수

    for j in l:
        if j == "(":
            num += 1
        elif j == ")":
            num -= 1
        if num < 0:  # 닫는 괄호가 여는 괄호보다 많으면 NO(예외 케이스 처리)
            valid = False
            break

    if valid and num == 0:
        print("YES")  # 괄호가 짝이 맞으면 YES
    else:
        print("NO")  # 짝이 맞지 않으면 NO

 

 

❓ 스택을 활용한 python 풀이

import sys

T = int(sys.stdin.readline().strip())  # 테스트 케이스 수 입력
for _ in range(T):
    l = sys.stdin.readline().strip()  # 괄호 문자열 입력
    stack = []  # 스택 초기화
    valid = True  # 유효한지 여부를 나타내는 플래그

    for char in l:
        if char == "(":
            stack.append("(")  # 여는 괄호는 스택에 추가
        elif char == ")":
            if stack:
                stack.pop()  # 닫는 괄호일 때, 스택에서 여는 괄호를 제거
            else:
                valid = False  # 스택이 비어있다면 유효하지 않음
                break

    if valid and not stack:  # 스택이 비어있어야 짝이 맞음
        print("YES")
    else:
        print("NO")