/<BOJ 백준 9012번> 괄호 - Java

문제 9012번 : 괄호

문제 해설

괄호 검사 문제는 자료구조 스택(Stack)을 사용하는 대표적인 문제이다. 본 문제 또한 스택을 이용하여 어렵지 않게 풀 수 있었다. 문제 해결 아이디어는 다음과 같다.

1. 괄호 '(' 가 오면 스택에 추가(push)한다.
2. 괄호 ')' 가 오면 스택 내부에 "(" 가 있는지 없는지 검사한다.
2-1. "(" 가 없으면 거짓임이다.
3. 제일 최근에 삽입된 "(" 를 스택에서 제거(pop)한다.
4. 위 2, 3번 과정을 테스트 케이스 수 T회 반복한다.
5. T번 반복 후 스택 내부에 괄호 "(" 가 있는지 없는지, 즉 스택이 비어있는지 확인한다.

 

이를 코드로 나타내면 다음과 같다.

 

private static boolean isBalanced(String str) {
    Stack<Character> stack = new Stack<>();

    for (char c : str.toCharArray()) {
        if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            if (stack.isEmpty()) {
                return false;
            }
          stack.pop(); 
        }
    }
    return stack.isEmpty(); 
}

 

위 코드는 str의 길이를 N이라고 가정했을 때, N의 크기 만큼 괄호 검사를 반복하므로 시간복잡도 O(N)을 갖는다.

코드

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

public class Main {

	public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            String str = br.readLine();
            if (isBalanced(str)) {
            	System.out.println("YES");
            } else {
            	System.out.println("NO");
            }
        }
    }

        private static boolean isBalanced(String str) {
        Stack<Character> stack = new Stack<>();

        for (char c : str.toCharArray()) {
            if (c == '(') {
            	stack.push(c);
            } 
            else if (c == ')') {
            	if (stack.isEmpty()) {
            		return false;
            	}
            stack.pop(); 
            }
        }
        return stack.isEmpty(); 
	}
	
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}
}