이번 문제는 stack을 활용하는 문제였으나 내가 풀 때는 stack을 쓰지 않고 풀었다.
괄호를 배열로 저장한다음
왼쪽 괄호와 오른쪽 괄호가 나올때 count를 올리거나 내렸다 그래서 만약 오른쪽 괄호가 한번 더 나오는 상황이 나오면 그것도 NO로 출력이 되게 했다.
오른쪽 괄호가 왼쪽 괄호보다 많아지는 상황에 대한 처리를 고민하느라 조금 어려웠다.
package S4_Baekjoon;
import java.util.Scanner;
public class Baekjoon9012 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
String[] VPS = new String[T];
for(int i = 0; i < T; i++){
VPS[i] = sc.next();
}
for(int i = 0; i < T; i++){
int count = 0;
for(int j = 0; j < VPS[i].length(); j++) {
if (VPS[i].charAt(j) == '(') {
count++;
} else if(VPS[i].charAt(j) == ')'){
count--;
if(count < 0){
break;
}
}
}
if(count == 0){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
}
밑에 있는 코드는 내 코드를 stack을 활용해서 푸는 코드이다
package S4_Baekjoon;
import java.util.Scanner;
import java.util.Stack;
public class Baekjoon9012 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
String[] VPS = new String[T];
for (int i = 0; i < T; i++) {
VPS[i] = sc.next();
}
for (int i = 0; i < T; i++) {
Stack<Character> stack = new Stack<>();
boolean isVPS = true;
for (char c : VPS[i].toCharArray()) {
if (c == '(') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty()) {
isVPS = false;
break;
} else {
stack.pop();
}
}
}
if (!stack.isEmpty()) {
isVPS = false;
}
if (isVPS) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
이 코드는 각 T의 케이스마다 스택을 새로 만들고 괄호 문자열의 각 문자를 확인하면서 "(" 를 만나면 스택에 푸시
")"를 만나면 스택에서 pop한다. 근데 스택이 비어있는데 ")"가 또 나오거나 모든 괄호를 확인했을때 스택이 비어있지 않으면 그것도 NO를 출력하는 코드이다
예시 케이스
2
(())())
(((()())()
(())())에 대한 예시:
(())())에 대한 시각적 표현:
시작: Stack = [] (empty stack)
문자 '('가 들어오면 Stack에 push: Stack = ['(']
두번째 문자 '('가 들어오면 Stack에 push: Stack = ['(', '(']
세번째 문자 ')'가 들어오면 Stack에서 pop: Stack = ['(']
네번째 문자 ')'가 들어오면 Stack에서 pop: Stack = []
다섯번째 문자 '('가 들어오면 Stack에 push: Stack = ['(']
여섯번째 문자 ')'가 들어오면 Stack에서 pop: Stack = []
일곱번째 문자 ')'가 들어오면, Stack에서 pop을 시도하나 Stack이 비어있음: Stack = []
'(((()())())'에 대한 예시:
시작: Stack = [] (empty stack)
첫번째 문자 '('가 들어오면 Stack에 push: Stack = ['(']
두번째 문자 '('가 들어오면 Stack에 push: Stack = ['(', '(']
세번째 문자 '('가 들어오면 Stack에 push: Stack = ['(', '(', '(']
네번째 문자 '('가 들어오면 Stack에 push: Stack = ['(', '(', '(', '(']
다섯번째 문자 ')'가 들어오면 Stack에서 pop: Stack = ['(', '(', '(']
여섯번째 문자 '('가 들어오면 Stack에서 push: Stack = ['(', '(', '(', '(']
일곱번째 문자 ')'가 들어오면 Stack에 pop: Stack = ['(', '(', '(']
여덟번째 문자 ')'가 들어오면 Stack에서 pop: Stack = ['(', '(']
아홉번째 문자 '('가 들어오면 Stack에서 push: Stack = ['(', '(', '(']
열번째 문자 ')'가 들어오면, Stack에서 pop: Stack = ['(', '(']
열한번째 문자 ')'가 들어오면, Stack에서 pop: Stack = ['(']