[JAVA] 백준 9012번 괄호 : 스택의 용도

9012번: 괄호

 

1. 문제 추상화

 

'(' 와 ')' 만으로 이루어진 문자열을 PS라 부른다. 그리고 괄호가 열리고 온전히 닫히는 PS를 VPS라 부른다. 주어진 PS 중 VPS를 구분하라. 

 

2. 알고리즘

 

조금 고민했다. 그리고 한 가지 개념이 스쳐지나갔다. 바로 '스택(Stack)'이다.

 

VPS는 두 가지 특성이 있다.

 

1. 나중에 열린 괄호가 먼저 닫혀야 한다.

2. 모든 열린 괄호는 닫혀야 한다. 

 

1번은 LIFO의 특징이다. 그러므로 스택과 알맞다. 그리고 2번은 스택이 비워있는지를 확인하면 된다.

 

 

열린 괄호가 나오면 스택에 Push 한다.

 

 

닫힌 괄호가 나오면 POP 한다.

 

만약 닫힌 괄호가 나왔는데 스택이 비워져있거나

PS 문자열의 모든 괄호를 검사했는데 스택에 아직 열린 괄호가 남아있다면

 

VPS가 아니다.

 

이처럼 스택은 LIFO 특성이 있는 패턴에 자주 사용된다.

 

3. 코드

 

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

public class Main {
	public static StringTokenizer stz;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		stz = new StringTokenizer(br.readLine());
		int size = Integer.parseInt(stz.nextToken());
		String[] PS = new String[size];
		
		for(int i=0; i<size; i++) {
			stz = new StringTokenizer(br.readLine());
			PS[i] = stz.nextToken();
		}
		
		for( String value : PS) {
			if(isVPS(value)) sb.append("YES").append("\n");
			else sb.append("NO").append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	// STACK으로 VPS 검사
	public static boolean isVPS(String value) {
		Stack<Character> openPSStack = new Stack<Character>();
		
		for(int i=0; i<value.length(); i++) {
			char ps = value.charAt(i);
			if(ps == '(') openPSStack.push(ps);
			else if(ps == ')') {
				if(openPSStack.isEmpty()) return false;
				else openPSStack.pop();
			}
		}
		
		if(openPSStack.isEmpty()) return true;
		else return false;
	}

}