일반적으로 아는 괄호 수식의 원리를 이해하면 풀 수 있는 문제이다.
'(' 여는 괄호가 있으면 ')'닫는 괄호가 있어야 한다는 것인데,
이것을 스택으로 적용한다면 '('때는 스택에 push하고 ')'때는 pop을 하면 된다.
그럼 이때 생기는 3가지의 경우의 수를 알아보자
예시 : (()())((()))
이렇게 완전한 수식인 경우 리턴 후 스택에 아무 것도 없어야 한다.
괄호가 남는 경우 ( '('가 많은 경우 )
리턴 후 '('가 스택에 남아있다.
괄호가 부족한 경우 ( ')'가 많은 경우 )
리턴 후 ')'가 스택에 남아있다.
import java.util.Scanner;
import java.util.Stack;
public class Num9012 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i =0; i<T; i++) {
System.out.println(solve(sc.next()));
}
}
private 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()) {
return "NO";
}
else {
stack.pop();
}
}
if (stack.empty()) {
return "YES";
} else {
return "NO";
}
}
}
참고 : https://st-lab.tistory.com/178
출처 : https://www.acmicpc.net/problem/9012