자바[JAVA] - 백준 9012번 괄호

이번에 풀어본 문제는 9012번 괄호 문제이다.

[문제]

괄호 기호를 입력받아 해당 문자열이 VPS인지 아닌지 판별하는 문제이다.

여기서 말하는 VPS는 '(' 기호가 ')'로 '()' 한 쌍을 이루는 것을 말한다. 

즉, '(' 괄호가 열리고 ')' 괄호가 모두 닫혀있는지 확인하면 된다. 따라서 문자열의 처음이 ')'가 나오면 안되고 무조건 '('로 시작하고 '()' 열리고 닫히는 괄호가 한 쌍을 이루었을 때 남아있는 기호가 없으면 된다.

 

이 문제를 Stack을 이용하여 풀었다.

위 그림처럼 문자열을 입력받고 한 문자씩 Stack에 집어 넣는 것으로 시작한다.

문자를 확인했을 때 '(' 문자가 나오면 Stack.push를 하고 ')' 문자가 나오면 Stack.pop으로 Stack의 문자를 제거한다.

 

그렇다면 시작 문자가 ')'가 나오게 된다면 어떻게 해야될까?

')'로 시작하게 된다면 Stack에 ')' 문자를 넣고 'NO'를 출력한 다음 종료하게 만들었다.

 

소스코드는 다음과 같다.

 

[소스코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class M9012 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());
        for(int i = 0;i < n;i++) {
            String[] s = bf.readLine().split("");
            Stack<String> stack = new Stack<>();

            for(int j =0;j < s.length;j++) {
                if(s[j].equals("(")) {
                    stack.push(s[j]);
                }
                else if(stack.empty()) {
                    stack.push(s[j]);
                    break;
                }
                else {
                    stack.pop();
                }
            }
            if(stack.empty()) {
                System.out.println("YES");
            }
            else {
                System.out.println("NO");
            }
        }
    }
}

[해석]

1. 몇 개의 문자열을 받을 것인지 입력받는다.

2. 입력 받은 횟수 만큼 반복 실행한다.

3. 문자열을 입력받고 해당 문자열을 한 문자씩 잘라서 배열에 넣는다.

4. 배열의 크기 만큼 반복하여 VPS인지 확인한다.

5. 첫 문자가 '(' 라면 Stack.push 한다. (Stack이 비어있다면 초기 문자라는 것이다.)

6. '(' 가 아니라면 Stack에 ')' 를 넣고 종료시킨다.

7. 5, 6의 경우가 아니라면 Stack.pop한다.

8. 한 개의 문자열을 실행했을 때 Stack이 비어있다면 VPS이므로 'YES'를 출력하고 비어있지 않다면 'NO'를 출력한다.

 

이 문제에서 고려해야하는 한 가지는 첫 문자가 ')' 였을 때 처리하는 과정이다.

해당 부분을 ')' Stack.push 함으로써 예외 처리 하였다.

 

문제는 생각보다 간단하지만 위에서 말한 한 가지만 잘 고려한다면 쉽게 풀 수 있는 문제이다.

 

[꿈은 크게 가져라, 부서져도 그 조각이 크게]