9012번: 괄호 [Python]

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입력 1 복사

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1 복사

NO
NO
YES
NO
YES
NO

예제 입력 2 복사

3
((
))
())(()

예제 출력 2 복사

NO
NO
NO

---

✅ 9012번 괄호 문제 풀이 과정 (백준)

문제 유형: 스택 (Stack) / 문자열 처리
추천 알고리즘: 스택(Stack) 활용
시간 복잡도: O(N)O(N)O(N) (한 번만 문자열을 순회하면 됨)

---

1️⃣ 문제 분석

올바른 괄호 문자열(VPS)인지 판별하는 문제입니다.
VPS의 조건:

1. (가 나오면 스택에 넣는다.
2. )가 나오면 스택에서 (를 제거한다.
3. 모든 문자열을 확인한 후 스택이 비어 있어야 VPS이다.
4. 중간에 )가 나왔을 때, 짝을 맞출 (가 없다면 VPS가 아니다.

예제 입력 1

 

6
(( 
)) 
(()) 
()()() 
(()())() 
()()(

 

예제 출력 1

 

NO 
NO 
YES 
YES 
YES 
NO

---

2️⃣ 해결 방법 (알고리즘)

이 문제를 해결하기 위해 스택(Stack) 자료구조를 사용하면 효율적입니다.

🔹 스택을 활용하는 이유

• 괄호의 짝을 맞추는 문제는 후입선출(LIFO, Last In First Out) 구조가 적합합니다.
• (를 만나면 스택에 넣고, )를 만나면 스택에서 (를 꺼내면 됩니다.
• 문자열을 한 번만 순회하면서 유효성을 판단할 수 있어 O(N)의 시간 복잡도로 해결할 수 있습니다.

---

3️⃣ 문제 해결 과정

1. 입력값을 읽고 문자열을 하나씩 확인
   • (이면 스택에 추가
   • )이면 스택에서 (를 제거
   • 만약 )가 나왔는데 스택이 비어 있다면 VPS가 아님 (NO 반환)
2. 문자열을 모두 확인한 후
   • 스택이 비어 있으면 VPS → "YES" 출력
   • 스택에 (가 남아 있으면 VPS가 아님 → "NO" 출력

---

4️⃣ Python 코드

 

import sys

def is_vps(s):
    stack = []
    for char in s:
        if char == '(':  # 열린 괄호면 스택에 추가
            stack.append(char)
        elif char == ')':  # 닫힌 괄호면 짝이 맞는지 확인
            if not stack:  # 스택이 비어 있으면 짝을 맞출 수 없음
                return "NO"
            stack.pop()  # 짝을 맞추면 스택에서 제거
    
    return "YES" if not stack else "NO"  # 스택이 비어 있으면 VPS

# 입력 처리
n = int(sys.stdin.readline().strip())  # 테스트 케이스 개수
for _ in range(n):
    s = sys.stdin.readline().strip()  # 괄호 문자열 입력
    print(is_vps(s))

---

5️⃣ 코드 상세 설명

🔹 is_vps() 함수 (VPS 판별)

def is_vps(s):
    stack = []  # 스택 초기화
    for char in s:
        if char == '(':
            stack.append(char)  # 열린 괄호는 스택에 추가
        elif char == ')':
            if not stack:  # 닫는 괄호가 나왔을 때 스택이 비어 있다면 NO
                return "NO"
            stack.pop()  # 열린 괄호와 짝을 맞춰 제거
    return "YES" if not stack else "NO"  # 스택이 비어 있으면 YES, 남아 있으면 NO

 

동작 과정

• (를 만나면 스택에 넣음
• )를 만나면 스택에서 (를 하나 꺼냄 (짝을 맞춤)
• 중간에 )가 나왔을 때 스택이 비어 있으면 VPS가 아니므로 "NO" 반환
• 문자열을 다 확인한 후 스택이 비어 있으면 VPS이므로 "YES", 남아 있으면 "NO"

---

6️⃣ 예제 실행 과정

입력 예제 1

 

6 
(( 
)) 
(()) 
()()() 
(()())() 
()()(

동작 과정

1. (( 처리
   • '(' → 스택 ['(']
   • '(' → 스택 ['(', '(']
   • 문자열 끝 → 스택이 남아 있음 → "NO"
2. )) 처리
   • ')' → 스택 비어 있음 → "NO"
3. (()) 처리
   • '(' → 스택 ['(']
   • '(' → 스택 ['(', '(']
   • ')' → 스택 ['(']
   • ')' → 스택 []
   • 문자열 끝, 스택 비어 있음 → "YES"
4. ()()() 처리
   • '(' → 스택 ['(']
   • ')' → 스택 []
   • '(' → 스택 ['(']
   • ')' → 스택 []
   • '(' → 스택 ['(']
   • ')' → 스택 []
   • 문자열 끝, 스택 비어 있음 → "YES"
5. (()())() 처리
   • '(' → 스택 ['(']
   • '(' → 스택 ['(', '(']
   • ')' → 스택 ['(']
   • '(' → 스택 ['(', '(']
   • ')' → 스택 ['(']
   • ')' → 스택 []
   • 문자열 끝, 스택 비어 있음 → "YES"
6. ()()( 처리
   • '(' → 스택 ['(']
   • ')' → 스택 []
   • '(' → 스택 ['(']
   • ')' → 스택 []
   • '(' → 스택 ['(']
   • 문자열 끝, 스택에 ( 남아 있음 → "NO"

---

7️⃣ 시간 복잡도 분석

• 스택 연산 (push/pop)은 O(1)
• 문자열을 한 번 순회하는 O(N)
• 테스트 케이스 개수 T를 고려하면 최종 시간 복잡도는 O(T * N)
  (각 문자열을 최대 50개까지 주어질 수 있으므로 충분히 빠름)

---

8️⃣ 결론

✅ 이 문제를 해결하는 최적의 방법은 "스택을 활용한 괄호 짝 검사"입니다.
✅ 시간 복잡도 O(N)으로 한 번만 문자열을 순회하며 해결 가능합니다.
✅ 스택 자료구조를 활용하면 효율적으로 VPS를 판별할 수 있습니다.

---

📌 추가 개선점
만약 스택 없이 단순한 카운터 변수만을 사용하여 (와 )의 개수를 세는 방식으로도 풀 수 있지만, 스택을 이용하면 더 직관적으로 짝을 맞출 수 있습니다.