[백준] 9012 괄호 - Data Structure / Java

• 문제 링크

9012번: 괄호

 

• 풀이 과정

문제에 제시된 조건에 의해 올바른 괄호 문자열이 되기 위해선

여는 괄호 '(' 가 존재 시 반드시 이에 대응하는 닫는 괄호 ')' 가 존재하여야 한다.

 

기본적으로 올바른 괄호는 여는 괄호에서 시작되고 입력받은 문자가 여는 괄호일 시 스택에 순차적으로 push(),

닫는 괄호일 시 스택에 쌓여있는 여는 괄호 하나를 pop() 하여

해당 괄호가 열고 닫는 괄호 쌍으로써 존재하는 지 검사한다.

 

모든 괄호를 검사 후 최종적으로 스택이 비어져있다면 온전한 수식임을 의미하여 "YES"를 반환하고

스택에 남은 괄호가 존재한다면 여는 괄호는 있지만 닫는 괄호는 없는 경우가 존재하므로 "NO"를 반환한다.

 

추가적으로 이미 스택이 비어있는 상황에서 추가적으로 닫는 괄호가 입력될 경우,

이는 닫는 괄호의 개수가 더 많다는 의미로 이 또한 "NO"를 반환하도록 분기를 걸어 검사한다.

 

• 풀이 코드

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

public class Main {

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

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

		for (int i = 0; i < t; i++) 
			bw.write(valid(br.readLine()) + "\n");

		bw.flush();
	}

	private static String valid(String input) {
		Stack<Character> stk = new Stack<>();
		
		for (Character c : input.toCharArray()) {
			if (c == '(')
				stk.push(c);
			else if (stk.empty())
				return "NO";
			else
				stk.pop();
		}

		if (!stk.empty())
			return "NO";
		else
			return "YES";
	}

}