백준 - (9012)괄호

 

---

이번 문제는 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 = ['(']