백준 4949 - 균형잡힌 세상

Java

4949 번 - 균형잡힌 세상

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호(“()”) 와 대괄호(“[]”)로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호(“(“)는 오른쪽 소괄호(“)”)와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호(“[“)는 오른쪽 대괄호(“]”)와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

문제 출처

접근 방법

왼쪽 괄호면 저장하고, 오른쪽 괄호이면 가장 최근에 삽입한 괄호가 같은 종류의 왼쪽 괄호이면 지우고, 아니면 종료하여 균형잡힌 문자열이 아니라고 판별한다.
즉, [ ( ] ) 인 경우도 균형잡힌 문자열이 아니라고 판별한다.

구현

(와 [ 같이 왼쪽 괄호이면 stack에 저장한다.
]이 왔을 때, stack의 top에 [가 아니라면, pair가 아니므로 종료 맞으면 [을 삭제하여 다음 괄호를 비교하기 위해 pair를 삭제한다. )도 마찬가지 이다.

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk; 
    	Stack<Character> st = new Stack<Character>();
    	boolean bl = true;
    	while(true) {
    		String str = br.readLine();
    		if(str.equals("."))
    			break;
    		for(int i = 0; i < str.length(); i++) {
    			char c = str.charAt(i);
    			if(c == '[' || c == '(') {
    				st.push(c);
    			}
    			else if(c == ']') {
    				if(!st.empty() && st.peek() == '[') {	// 짝이 맞다면
    					st.pop();							//'['를 삭제함
    				}
    				else {									// 아니면 종료
    					bl = false;
    					break;
    				}
    			}
    			else if(c == ')') {
    				if(!st.empty() && st.peek() == '(') {
    					st.pop();
    				}
    				else {
    					bl = false;
    					break;
    				}
    			}
    		}
    		if(bl && st.empty())
    			System.out.println("yes");
    		else {
    			System.out.println("no");
    			bl = true;
    		}
    		st.clear();
    	}
    	br.close();
    }
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐★★★★

후기

프로그래머스에서 stack을 공부 할 때 풀었던 문제이다.

개선할 점

없