백준 9012 / 괄호

문제

풀이

설명

일반적으로 아는 괄호 수식의 원리를 이해하면 풀 수 있는 문제이다.
'(' 여는 괄호가 있으면 ')'닫는 괄호가 있어야 한다는 것인데,
이것을 스택으로 적용한다면 '('때는 스택에 push하고 ')'때는 pop을 하면 된다.

그럼 이때 생기는 3가지의 경우의 수를 알아보자

1. 예시 : (()())((()))
   
   이렇게 완전한 수식인 경우 리턴 후 스택에 아무 것도 없어야 한다.

2. 괄호가 남는 경우 ( '('가 많은 경우 )
   
   리턴 후 '('가 스택에 남아있다.

3. 괄호가 부족한 경우 ( ')'가 많은 경우 )
   
   리턴 후 ')'가 스택에 남아있다.

코드

import java.util.Scanner;
import java.util.Stack;

public class Num9012 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int i =0; i<T; i++) {
			System.out.println(solve(sc.next()));
		}
	}

	private static String solve(String s) {
		
		Stack<Character> stack = new Stack<>();
		
		for(int i = 0; i< s.length(); i++) {
			char c = s.charAt(i);
			
			if (c == '(') {
				stack.push(c);
			}
			else if (stack.empty()) {
				return "NO";
			}
			else {
				stack.pop();
			}
		}
		
		if (stack.empty()) {
			return "YES";
		} else {
			return "NO";
		}
	}
}

참고 : https://st-lab.tistory.com/178
출처 : https://www.acmicpc.net/problem/9012