[백준] 9012번 : 괄호 (JAVA)

스택 관련 5문제 중 벌써 3번째 문제인  9012번 : 괄호 문제를 풀었다.

 

 

스택에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/17

[자료구조] 스택 (Stack)

 

바로 앞 문제인 10773번 : 제로 에 대한 내용은 바로 앞의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/19

[백준] 10773번 : 제로 (JAVA)

 

---

<문제>

 

<문제 해석>

스택을 이용하여 

주어진 괄호 문자열이 올바른 괄호 문자열(VPS) 인지 판단해라.

- 올바른 괄호면 YES  /  올바르지 않다면 NO 출력

 

 

 

<문제 해결>

이 문제 또한, 스택 관련 문제이다.

스택에 대해 이해하고 있다면 어렵지 않게 풀었을 것이다.

 

현재 문제에서 괄호는 ' ( ' , ' ) ' 두 종류만 있다.

stack을 이용하여 문제를 풀 수 있다.

 

<알고리즘>

1. 문자열이 ' ( ' 일 때, stack에 해당 문자열을 push 한다.

 

2. 문자열이 ' ) ' 일 때, stack의 맨 위 문자열을 확인하고,

 

                 1. stack의 맨위 문자열을 pop() 한다.

                     - ' ) ' 문자와 괄호 짝을 이뤘기 때문이다.

 

                 2. 해당 stack이 비었을 경우에는 올바른 괄호가 아니다.

                     - ' ) ' 문자열이 짝을 이룰 수 있는 괄호가 없기 때문이다.

 

 

올바른 괄호인지 판별하기 위해서는 

1가지 조건이 더 필요하다.

 

3. 문자열의 첫번째 문자가 ' ) ' 일 경우에는 올바른 괄호가 아니다.

      * ' ) ' 괄호가 ' ( ' 괄호보다 먼저 올 수 없기 때문이다.*

 

 

 

 

<코드>

import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;

public class Main {	

	static String str;
	static String result;

	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		for(int i=0;i<n;i++) {
			str = sc.next();
			run();
			System.out.println(result);

		}
	}
	
	static void run() {
		Stack<Character> stack = new Stack<>();
        
		result = "NO";
        
		if(str.charAt(0)== ')'){
			result = "NO";
			return;
		}
		
		for(int i=0;i<str.length();i++) {
			char s = str.charAt(i);
			
			
			if(s == '(') {
				stack.push(s);
			}
			else if(s == ')') {
				
				if(stack.empty()) {
					result = "NO";
					return;
				}else {
					stack.pop();
				}
			}
		}
		if(stack.size() == 0) {
			result = "YES";
		}	
	}
}

 

 

---

https://www.acmicpc.net/problem/9012

9012번: 괄호