메모
/*
PS = 괄호 문자열 (, )
VPS = 올바른 괄호 문자열
기본 VPS = ()
예시 1.
x = VPS 일 때
(x) = VPS 이다.
예시 2.
x = VPS, y = VPS 일 때
xy = VPS 이다.
예시 3.
(())() = VPS, ((())) = VPS 일 때
(()( != VPS, (())())) != VPS, (() != VPS 이다
--> () 이렇게 쌍이 맞지 않기 때문
올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력
*/
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int i = 0; i < T; i++) {
System.out.println(solve(in.next())); // nextLine() 은 사용 X
}
}
public static String solve(String s) {
Stack<Character> stack = new Stack<>(); // 스택 사용
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') { // '(' 일 경우 : 스택에 넣는다.
stack.push(c);
} else if (stack.empty()) { // ')' 을 push 한 경우 中 pop할 원소가 없을 경우 : '(' 개수 < ')' 개수 이므로, "NO"
return "NO";
} else { // ')' 을 push 한 경우 : '(' 개수 == ')' 개수 이므로, 스택의 원소를 반환 및 삭제한다.
stack.pop();
}
}
// stack 의 push, pop 이후
if (stack.empty()) { // 스택이 비어있으면, YES -> 온전한 수식이기 때문
return "YES";
} else { // 스택에 잔여 요소가 있으면, '(' 개수 > ')' 개수 이므로, "NO"
return "NO";
}
}
}
scanner
'(' 를 기준으로 추가적으로 ')'를 붙이는 방식 (3가지 경우)
'(' 개수 == ')' 개수 : 올바른 괄호 문자열
'(' 개수 > ')' 개수 : '(' 가 pop으로 지워지지않아 스택 안에 '(' 가 여전히 남아있게 된다.
'(' 개수 < ')' 개수 : 이미 비어있는 스택에서 pop을 하므로 에러(EmptyStackException) 발생
참고: [백준] 9012번 : 괄호 - JAVA [자바]