[Java] 3단계. 괄호 [9012번]

https://www.acmicpc.net/problem/9012

• 예제 입력1

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

• 예제 출력1

NO
NO
YES
NO
YES
NO

• 예제 입력2

3
((
))
())(()

• 예제 출력2

NO
NO
NO

---

• 문제 접근
  • 괄호가 쌍이 맞으면 VPS(Valid PS)
  • 괄호 쌍이 아니면 VPS가 아님
  • 입력
    
    • 첫째 줄 : T개의 케이스가 주어짐
    • ~ T번째 줄 : 괄호 문자열 (2 <= 길이 <= 50)
  • 출력
    
    • VPS면 YES, VPS가 아니면 NO를 한 줄에 하나씩 출력
• 문제 해결
  
  • 전형적인 스택 문제
    1. 입력받은 문자열을 모두 Stack에 추가
    2. 새로운 Stack 준비
    3. 기존 Stack이 isEmpty()가 될 때까지 반복
    4. 기존 Stack에서 pop을 한 괄호가 ')'라면 새로운 Stack에 Push
    5. 기존 Stack에서 pop을 한 괄호가 '('라면 새로운 Stack Pop (새로운 스택에는 ')' 괄호만 추가되어 있을 것)
       단, '('와 짝이 없다면 = 새로운 Stack이 비어있다면 '('를 push하고 break → 불필요한 반복을 줄임
    6. 최종적으로 새로운 Stack이 비어있다면 YES, 아니라면 NO를 StringBuilder에 추가
• 기존 풀이 [메모리 : 14,300 KB / 시간 : 112 ms]

public static void main(String[] args) throws IOException{
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int T = Integer.parseInt(br.readLine());
    for(int i = 0; i < T; i++){
        Stack<Character> originStack = new Stack<>();
        Stack<Character> newStack = new Stack<>();

        String input = br.readLine();
        int length = input.length();
        for(int j = 0; j < length; j++){
            originStack.push(input.charAt(j));
        }

        while(!originStack.isEmpty()){
            char ch = originStack.pop();
            if(ch == ')')
                newStack.push(ch);
            else {
                if(newStack.isEmpty()){
                    newStack.push(ch);
                    break;
                }
                newStack.pop();
            }
        }

        if(newStack.isEmpty()) sb.append("YES");
        else sb.append("NO");
        sb.append("\n");
    }
    System.out.println(sb);
}

• ChatGPT 풀이 [메모리 : 14,280 KB / 시간 : 112 ms]

public static void main(String[] args) throws IOException{
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int T = Integer.parseInt(br.readLine());
    for(int i = 0; i < T; i++) {
        String input = br.readLine();
        sb.append(isValid(input) ? "Yes" : "No").append("\n");
    }

    System.out.println(sb);
}

private static boolean isValid(String str) {
    int length = str.length();
    int count = 0;

    for(int i = 0; i < length; i++){
        char ch = str.charAt(i);
        if(ch == '(') count++;
        else count--;

        if(count < 0) return false;
    }

    return count == 0;
}

---

• ChatGPT의 풀이를 보고나니 굳이 Stack을 두 개나 쓸 필요가 없음
  1. 입력받은 String 길이만큼 반복
  2. '('일 경우 무조건 push하고, ')' 괄호일 경우 스택이 비어있지 않다면 pop, 스택이 비어있을 경우 VPS가 아니므로 반복문 종료
  3. 또한, 반복문이 종료되었을 시점에 Stack이 비어있지 않다면 VPS가 아님
• Stack 1개로 풀이 [메모리 : 14,400 KB / 시간 : 112 ms]

public static void main(String[] args) throws IOException{
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int T = Integer.parseInt(br.readLine());
    for(int i = 0; i < T; i++) {
        boolean flag = true;
        Stack<Character> stack = new Stack<>();

        String input = br.readLine();
        int length = input.length();
        for(int j = 0; j < length; j++){
            char ch = input.charAt(j);
            if(ch == '(') {
                stack.push(ch);
            } else {
                if(stack.isEmpty()) {
                    flag = false;
                    break;
                }
                stack.pop();
            }
        }
        if(!stack.isEmpty()) flag = false;
        sb.append(flag ? "YES" : "NO").append("\n");
    }

    System.out.println(sb);
}