출처 : Unsplash

[백준] 9012번: 괄호

저번 시간에 이어 스택을 활용한 문제를 풀어 보자.

📌 목차

1. 설명
2. 접근 방식
3. 코드

📌 설명

이 문제는 괄호로만 주어진 문자열에서, 해당 문자열이 완전한 형태의 괄호 ()로만 이루어진 '올바른 괄호 문자열(Valid Parenthesis String)'인지 아닌지를 판별하는 문제이다.

📌 접근 방식

• 주어진 문자열을 새 스택에 계속 담아 ()가 생길 때마다 없애야 하는 방식이다.
• 문자열을 끝까지 순회하면서 그 스택이 빈 문자열이면 완전하므로 True를,
• 아니면 불완전하므로False를 반한하면 된다.
  
  

📌 코드

• 아래처럼 스택을 직접 구현해서 풀어도 되지만
• 파이썬에서 기본적으로 제공되는 자료형인 list를 이용해도 쉽게 풀 수 있다.

import sys

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

# 자료 구조 스택 구현
class Stack():
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.empty():
            raise Exception("stack is empty.")
        self.items.pop()

    def top(self):
        if self.empty():
            raise Exception("stack is empty.")
        return self.items[-1]

    def empty(self):
        return not self.items

    def __str__(self):
        return str(self.items)

    def __len__(self):
        return len(self.items)

# T 입력
T = int(input())

# T만큼 반복
for _ in range(T):

    # 스택 변수 할당
    stack = Stack()

    # 한 줄마다 문자열 입력
    string = input()

    # 문자열의 각 괄호를 검사
    for parentheses in string:

        # '('일 경우 스택에 추가
        if parentheses == '(':
            stack.push(parentheses)
        # ')'일 경우 스택이 비어 있지 않으면 '(' 이 스택에 있으므로 스택의 '('를 제거
        elif parentheses == ')':
            if not stack.empty():
                stack.pop()
            # 스택이 비어 있으면 ')'가 먼저 오면 불완전하므로 "NO" 출력하고 for 문 탈출
            else:
                print("NO")
                break

    # 위의 for 문을 마친 이후 else 문을 실행
    else:
        # stack이 비어 있으면 완전하므로 "YES" 출력
        if stack.empty():
            print("YES")
        # stack이 비어 있지 않으면 불완전하므로 "NO" 출력
        else:
            print("NO")