🔄 백준 9012번 괄호 문제 풀이

1. 🛠️ 백준 온라인 저지 학습 환경 설정

1.1. 알고리즘 분류 숨기기

• 백준 문제 페이지 하단에 알고리즘 분류가 표시되어 있다.

• 이는 문제 풀이에 대한 스포일러가 될 수 있어 학습 효과를 저하시킨다.

• 설정 변경 방법:

2. 📝 백준 9012번 괄호 문제 개요

2.1. 문제 특성

• 괄호 문자열(PS)이 올바른 괄호 문자열(VPS)인지 판단하는 문제이다.

• 여러 개의 테스트 케이스로 구성되었다.

• 각 테스트 케이스마다 YES 또는 NO를 출력해야 한다.

2.2. VPS(Valid PS) 정의

• 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS이다.

• x가 VPS라면 “(x)”도 VPS이다.

• 두 VPS x와 y를 접합시킨 xy도 VPS이다.

• 예시: “(())()”와 “((()))”는 VPS이다.

• 반례: “(()(“, “(())()))”, “(()”는 VPS가 아니다.

3. 💡 문제 접근 방법

3.1. 스택 자료구조 활용

• 괄호 매칭 문제는 스택을 이용하는 전형적인 문제이다.

• 여는 괄호와 닫는 괄호의 매칭 관계가 후입선출(LIFO) 방식으로 이루어진다.

• 괄호 쌍 매칭 예시:

text괄호 매칭 순서:
(1 (2 (3 )3 )2 )1

4. 🧮 알고리즘 구현

4.1. 풀이 로직

• 여는 괄호(‘(‘)가 나오면 스택에 push한다.

• 닫는 괄호(‘)’)가 나오면:

• 모든 처리가 끝난 후:

4.2. 파이썬 코드 구현

pythonT = int(input())
for _ in range(T):
s = input()
stack = []
is_vps = True

for ch in s:
    if ch == '(':
        stack.append(ch)
    else:  # ch == ')'
        if stack:  # 스택이 비어있지 않으면
            stack.pop()
        else:  # 스택이 비어있으면
            is_vps = False
            break

if stack:  # 스택에 괄호가 남아있으면
    is_vps = False

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

5. 🧪 테스트 케이스 분석

5.1. 첫 번째 테스트 세트

– 입력: (())()), (((()())(), (()())((())), ((()()(()))(((())))(), ()()()()(()()())(), (()((())()(

– 출력: NO, NO, YES, NO, YES, NO

5.2. 두 번째 테스트 세트

– 입력: ((, )), ())(()

– 출력: NO, NO, NO

5.3. 예외 케이스 분석

• 여는 괄호만 있는 경우: 스택이 비어있지 않아 NO

• 닫는 괄호만 있는 경우: 비어있는 스택에서 pop 시도하여 NO

• 괄호 쌍이 맞지 않는 경우: 처리 과정에서 오류 발생하여 NO

6. 📊 결과 및 정리

6.1. 문제 해결 요약

• 괄호 문제는 스택 자료구조를 활용하여 효율적으로 해결하였다.

• 시간 복잡도: O(n) (n은 문자열 길이)

• 공간 복잡도: O(n) (최악의 경우 모든 괄호를 스택에 저장)

6.2. 핵심 학습 포인트

• 괄호 매칭 문제는 스택을 사용하는 대표적인 예시이다.

• 스택의 LIFO 특성이 괄호 쌍 매칭에 적합하다.

• 문제를 풀 때 예외 케이스 처리가 중요하다.