[BOJ 4949] 균형잡힌 세상 (Java)

문제

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

4949번: 균형잡힌 세상

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).

풀이

올바른 괄호문제랑 같은 방식으로 풀면 된다. 

 

1. 문자와 공백을 모두 없애준다. 

String replaceAll 첫 번째 인자에 정규식을 넣어서 구현을 했는데, 공백 문자를 표현하는 \s가 BOJ 자바 버전에서 파싱이 안된다.  공백 문자열을 그대로 넣어서 replace 하는 것으로 변경하였다.

//        s = s.replaceAll("[a-z]*[A-Z]*\s*", ""); // text block error

//        Pattern p = Pattern.compile("[a-z]*[A-Z]*\s*"); // text block error
//        Matcher m = p.matcher(s);
//        s = m.replaceAll("");

        s = s.replaceAll("[a-z]*[A-Z]*", "");
        s = s.replaceAll(" ", "");

 

괄호문자열을 순회하면서,

2. '(' '[' 왼쪽 괄호는 Stack에 넣어준다. 

 

3. ')', ']' 오른쪽 괄호가 나올 경우, Stack의 top이 해당 괄호와 짝을 이루는 왼쪽 괄호인지 체크하여 맞다면 top을 pop한다. 만약 top이 오른쪽 괄호와 짝을 이루지 않는다면 올바른 괄호가 아니므로 순회를 중단하고 No를 출력한다. 

4. 순회가 끝난 후 Stack에 비어있다면 올바른 괄호이므로 Yes 출력, 아니라면 No 출력

소스코드

package stack;

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

public class BOJ4949 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while(true){
            String s = br.readLine();
            if(s.equals(".")) break;

            if(solution(s.substring(0, s.length()-1))) bw.write("yes\n");
            else bw.write("no\n");
            bw.flush();
        }
    }

    public static boolean solution(String s){
        s = s.replaceAll("[a-z]*[A-Z]*", "");
        s = s.replaceAll(" ", "");

        Stack<Character> st = new Stack<Character>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '(' || c == '['){
                st.push(c);
            } else {
                if(st.isEmpty()){
                    return false;
                } else {
                    if((c == ']' && st.peek() == '[')||
                            ( c == ')' && st.peek() == '(')) {
                        st.pop();
                    } else {
                        return false;
                    }
                }
            }
        }
        if(st.isEmpty()) return true;
        return false;
    }
}