/ BOJ

BOJ_9012_괄호_JAVA

문제 : 괄호

링크 : BOJ_9012_괄호

접근 방식

스택을 이용해서 풀면 간단하게 풀 수 있다.

9012_1

위 이미지처럼, 값을 읽어와서 ‘(‘ 인 경우 스택에 쌓는다. 스택을 쌓던 도중 읽어들인 값이 ‘)’이라면, 스택의 최상단을 확인해 ‘(‘일 경우 pop 시켜 주도록 한다.

모든 문자열을 읽어들인 뒤 스택에 값이 남아있는지 여부를 확인해서 결과를 출력하면 된다.

풀이 방법

주어진 시행 횟수를 읽어들여 해당 횟수만큼 반복한다.

반복의 시작에 stack을 초기화시켜주고, 문자열을 읽어와 toCharArray 메서드를 이용해 char[]로 저장한다.

char[]을 탐색하면서 ‘(‘ 이라면 push를, ‘)’ 이라면 현재 스택의 top을 확인하여 ‘)’ 일 경우 pop한다.

반복이 모두 이루어진 후 스택이 비어있는 지 확인해서 비어있다면 YES를, 비어있지 않다면 NO를 출력한다.

소스 코드


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

public class BOJ_9012_괄호 {
	static ArrayList<Integer> stack = new ArrayList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int K = Integer.parseInt(in.readLine());

		for(int i=0;i<K;i++) {
			stack.clear();
			char[] chars = in.readLine().toCharArray();
			for(int j=0;j<chars.length;j++) {
				if(chars[j] == '(') {
					push('(');
				}else if(chars[j] == ')'){
					if(top() == '(') {
						pop();
					}else {
						push(')');
					}
				}
			}

			if(isEmpty()) {
				System.out.println("YES");
			}else
			{
				System.out.println("NO");
			}
		}
	}

	public static void push(int X) {
		stack.add(X);
	}

	public static void pop() {
		if(stack.size() == 0) {
		}else {
			stack.remove(stack.size()-1);
		}
	}

	public static void size() {
		System.out.println(stack.size());
	}

	public static boolean isEmpty() {
		if(stack.size() == 0) {
			return true;
		} else {
			return false;
		}
	}

	public static int top() {
		if(stack.size() == 0) {
			return -1;
		}else {
			return stack.get(stack.size()-1);
		}
	}
}