[알고리즘 PS] 백준 9012번 괄호 자바 문제 풀이

문제

해당 포스팅은 백준의 9012번 괄호 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

이번 문제는 스택의 아주 대표적인 문제라고 할 수 있는 괄호 검사 문제이다.

해당 문제에서는 2가지 기호에 따라서 스택이 진행하는 연산이 달라진다.

1. ( : 여는 괄호
2. ) : 닫는 괄호

여는 괄호

여는 괄호는 무조건 닫는 괄호와 짝이돤다.

그럼 여는 괄호가 등장했다는 소리는 언젠간 닫는 괄호가 등장할 것이다라는 의미로 해석할 수 있다.

우리는 이 여는 괄호를 스택에 넣고 닫는 괄호를 기다릴 것이다.

닫는 괄호

닫는 괄호는 절대 스스로 혼자 닫힐 수 없다.

닫는 괄호는 무조건 앞선 여는 괄호와 짝이 되어야 하는데, 만약 해당 닫는 괄호가 여는 괄호 없이, 즉 스택에 pop한 값이 없으면 정확히 말 해서 EmptyStackException()이 발생하면 해당 문장은 완전한 문장이 아니라고 판단해도 된다.

그래서 우리는 이 닫는 괄호를 만나면 스택에서 pop 연산을 수행하도록 할 것이다.

팁

여기서 다른 사람들의 풀이를 보면 boolean flag를 이용해서 exception이 발생하면 flag를 false로 변경시키고 마지막에 flag가 false인지 아닌지 검사하는 로직이 존재한다.

하지만 우리는 처음부터 정답 배열에 정답임을 저장하고, 만약 exception이 한 번이라도 발생되면 오답이라고 저장하고 마지막에 정답을 출력하도록 하자.

이런 방법이 조금 더효율적일 것 같다.

 

정답 코드

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());

        while(t-- > 0) {
            Stack<String> stack = new Stack<>();
            String answer = "YES";
            String[] n = br.readLine().split("");

            for (int i = 0; i < n.length; i++) {
                if(n[i].equals("(")) stack.push("(");
                else if(n[i].equals(")")) {
                    if(stack.isEmpty()) answer = "NO";
                    else stack.pop();
                }
            }
            if(!stack.isEmpty()) {
                answer = "NO";
            }
            bw.write(answer + "\n");
        }
        bw.flush();
        bw.close();
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.