[백준] 4949번: 균형잡힌 세상(스택, 문자열)

acmicpc.net/problem/4949

4949번: 균형잡힌 세상

코드

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));
		while(true) {
			
			String str = bf.readLine();
			if(str.equals("."))
				break;
			Stack<Character> s = new Stack<Character>();
			String result = "";
			boolean flag = true;
			for(int i=0; i<str.length(); i++) {
				
				/* 여는괄호 '(' 나 '[' 는 스택에 넣어준다. */
				if(str.charAt(i) == '(')
					s.push('(');
				
				else if(str.charAt(i) == '[')
					s.push('[');
				
				/* 닫는괄호 ')' 나 ']' 는 스택이 비어있거나 여는괄호와 짝이 안맞는경우 -> 탈출한다. */
				/* 스택이 비어있는경우 -> 입력이 ))] 와 같은경우, */
				/* 짝이 안맞는경우 -> (([) 와 같은 경우, */
				else if(str.charAt(i) == ')') {
					if(s.isEmpty() || s.peek() != '(') {
						flag = false;
						break;
					}
					s.pop();
				}
				else if(str.charAt(i) == ']') {
						if(s.isEmpty() || s.peek() != '[') {
							flag = false;
							break;
						}
						s.pop();
						
				}
			}
			
			// 스택이 비어있지 않으면 균형이 맞지 않는 경우
			if(!s.isEmpty())
				flag = false;
			result = (flag) ? "yes" : "no";
			System.out.println(result);
			
		}
		bf.close();
	}

}

풀이

괄호 열고 닫는문제 -> 스택을 쓰면 편할 것 같다고 생각했다.

 

여는괄호 - '(' 나 '[' 가 들어오면 스택에 쌓는다. (push)

 

닫는괄호 - ')' 나 ']' 가 들어오면 여는 괄호와 짝일경우 제거한다. (pop)

 

 * 닫는괄호가 나왔을때, 스택의 사이즈가 비어있거나 여는 괄호와 짝이 아닌경우 -> 중단(균형잡힌세상 X)

    - 스택의 사이즈가 비어있는경우 -> ") ] ]" 와 같이 여는 괄호 없이 닫는 괄호가 먼저 나오는경우

    - 짝이 아닌 경우 -> "[ [ [ ( ] ) 와 같이 닫는 괄호 ']' 인데 이전 문자는 '(' 여서 짝이 맞지 않음.

 

위 과정이 끝난후 스택이 비어있으면 -> 균형잡힌 세상