문제
괄호 문자열(PS, Parenthesis String)은 '('와 ')'로만 이루어진 문자열이다. 그 중 올바른 괄호 문자열(VPS, Valid Parenthesis String)은 열린 괄호와 닫힌 괄호의 짝이 완벽하게 맞는 문자열을 의미한다. 주어진 괄호 문자열이 VPS인지 판단하는 문제다.
입력
- 첫째 줄: 테스트 케이스 수 T
- 다음 T줄: 각각 괄호 문자열
출력
각 테스트 케이스마다 YES 또는 NO 출력
예제
| 입력 | 출력 |
|---|---|
4 (())()) (((()())) (()())((())) ((()()(()))((())) | NO NO YES YES |
풀이
스택 자료구조를 활용하여 괄호의 짝을 검사한다. ( 문자를 만나면 스택에 push하고, ) 문자를 만나면 스택에서 pop한다. 스택이 비어있는데 )를 만나거나, 모든 문자를 처리한 후 스택이 비어있지 않으면 유효하지 않은 문자열이다.
- T개의 테스트 케이스를 반복 처리한다.
- 각 문자열을 순회하며
(는 스택에 push,)는 스택에서 pop한다. )를 만났을 때 스택이 비어있으면 즉시"NO"로 판정한다.- 순회 완료 후 스택이 비어있으면
"YES", 남아있으면"NO"를 출력한다.
핵심 아이디어: 열린 괄호만 스택에 push하고, 닫힌 괄호를 만날 때마다 pop하여 짝이 맞는지 확인한다. 최종적으로 스택이 비어있어야 완벽한 VPS다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Day15BOJ9012괄호 { // 9012
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
Stack<Character> stack = new Stack<>();
for (int n = 0; n < N; n++) {
String ans = "YES";
String str = br.readLine();
stack = new Stack<>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '(')
stack.add(c);
else if (c == ')') {
if (stack.isEmpty() || stack.pop() != '(') {
ans = "NO";
break;
}
}
}
if (!stack.isEmpty())
ans = "NO";
sb.append(ans).append("\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N * L) — N은 테스트 케이스 수, L은 문자열 길이
- 공간: O(L) — 스택 최대 크기는 입력 문자열 길이