[백준] 9012번: 괄호(스택)

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

9012번: 괄호

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		
		for(int tc=0; tc<T; tc++) {
			String str = bf.readLine();
			Stack<Character> s = new Stack<Character>();
			boolean flag = true;
			
			for(int i=0; i<str.length(); i++) {
				// 현재 문자가 '(' 인 경우 스택에 저장
				if(str.charAt(i) == '(') 
					s.push('(');
				
				// 현재 문자가 ')' 인 경우
				else {
					if(s.isEmpty()) {	// 스택이 비어있으면 올바른 괄호 문자열이 아닌경우
						flag = false;
						break;
					}
					
					else if(s.peek() == '(') // 스택에 저장된 값이 '(' 인 경우 -> 제거
						s.pop();
					
					else if(s.peek() == ')') // 스택에 저장된 값이 ')' 인 경우 -> 저장
						s.push(')');
				}
			}
			
			if(!flag || !s.isEmpty())
				System.out.println("NO");
			else
				System.out.println("YES");
		}
		
		bf.close();
	}

}

풀이

괄호 처리하는 문제는 거의 대부분 스택으로 해결되는 것 같다.

() 쌍인경우 YES , 그렇지 않은경우 NO를 출력하는 문제.

 

현재 문자가 ' ( ' 인 경우 스택에 저장하고

현재 문자가 ' ) ' 가 오는 경우만 생각을 해주면 된다.

  - 스택이 비어있는 경우 -> ' ) ' 를 지울 수 없으므로 올바른 괄호 문자열이 아니다. 따라서 더 이상 반복문을 탐색할 필요 없이 flag를 false로 설정하고 종료한다.

  - 스택에 저장된 값(peek())이 ' ( ' 인 경우 -> '( )' 올바른 괄호 쌍이므로 스택에서 '('을 제거한다.(pop())

  - 스택에 저장된 값(peek())이 ' ) ' 인 경우 -> ' ) ' 를 스택에 저장한다.

 

 

 

그런데 코드를 보니... 현재 문자가 ' ) ' 가 오는 경우에서 저렇게 나누지 않아도 될 것 같았다.

문제에서는 ()(()) 와 같이 ' ) ' 문자가 연속으로 오는 경우가 존재하지만, Stack으로 해결하면 '()' 쌍이 오면 괄호쌍이 제거되므로 연속된 ' ) ' 가 올 수 없다.

따라서 현재 문자가 ' ) ' 인경우에 스택이 비어있거나, 이전 스택에 저장된 값이 ' ) ' 인경우 모두 NO 를 출력하면 된다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		
		for(int tc=0; tc<T; tc++) {
			String str = bf.readLine();
			Stack<Character> s = new Stack<Character>();
			boolean flag = true;
			
			for(int i=0; i<str.length(); i++) {
				// 현재 문자가 '(' 인 경우 스택에 저장
				if(str.charAt(i) == '(') 
					s.push('(');
				
				// 현재 문자가 ')' 인 경우
				else {
					// 스택이 비어있거나 스택에 저장된 값이 ')' 인 경우 - 올바른 괄호 문자 X
					if(s.isEmpty() || s.peek() == ')') {	
						flag = false;
						break;
					}
					
					else if(s.peek() == '(') // 스택에 저장된 값이 '(' 인 경우 -> 제거
						s.pop();
				}
			}
			
			if(!flag || !s.isEmpty())
				System.out.println("NO");
			else
				System.out.println("YES");
		}
		
		bf.close();
	}

}