자료구조[스택]_백준_4949

백준 스택 4949번

스택을 응용하는 알고리즘 문제입니다. 

풀이를 시작하기게 앞서 문제를 먼저 분석하여 접근해보겠습니다.

 

1. 동일한 괄호가 짝을 이루어야 한다. 

ㄴ> 두 개의 괄호를 구분해서 생각해줘야 합니다.

 

2. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 있다.

ㄴ> 반드시 왼쪽 괄호가 먼저 나와야만 짝을 이룰 수 있다. 

 

3. 짝을 이루는 문자열이 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

ㄴ>  균형이 이루어진 괄호 안에도 괄호가 있을 수 있는데 이 내부에 있는 괄호 또한 균형이 맞아야 합니다.

ㄴ> ( ] [ ) 이런 문자열도 외부 괄호는 균형을 이루지만 내부 괄호는 균형을 이루지 않기 때문에 조건에 맞지 않습니다.

 

위의 문제 분석을 통해 알아낼 수 있는 핵심중에서 이 문제를 해결하기 위한 키는 바로 1번과 3번을 보시면

소괄호나 대괄호 상관없이 괄호는 무조건 적어도 왼쪽 괄호부터 나와야 한다는 것을 알 수 있습니다.

마지막으로 입력되는 문자열, 영문 알파벳, 공백, 소괄호, 대괄호가 입력되는데 이 중에서 어떤 값을 스택에 저장할 것인지를 생각해봐야 합니다. 하지만 위에서 문제를 분석한 내용을 보시면 아시겠지만, 균형을 맞추기 위해 달성해야 하는 조건은 모두 괄호에 있기 때문에 스택에는 괄호를 저장하도록 하겠습니다. 

 

1. 스택에는 열린 괄호만 push한다.  (push 조건)

2. 계속 문자를 비교하면서 짝이 맞는 경우에만 pop한다. (pop 조건) 

3. 스택에 괄호가 남아 있다면 조건을 만족하지 못한 문자열이다. -> NO

결과적으로 push는 어렵지 않습니다. 다만 pop을 하는 조건만 한 번더 생각해주면 됩니다.

 

 

지금부터 조건문을 설계하는 과정을 보면서 경우의 수를 줄이는 방법을 함께 보겠습니다.  

 

1) if (문자 == '(' || 문자 == '[')

ㄴ> 문자열을 탐색하다가 가장 먼저 등장하는 왼쪽 괄호를 스택에 넣어줍니다. 
ㄴ> 이렇게 조건을 정해준 이유는 왼쪽 괄호가 나오기 전에 오른쪽 괄호가 먼저 나온다면 균형을 맞출 수 없습니다. 
ㄴ> EX :  ] n a s e ( ) 


2) else if(문자 == ')')

ㄴ> 오른쪽 소괄호가 먼저 나온 경우, 이제 앞에서 넣어준 괄호를 꺼내서 짝을 이뤄야합니다.
ㄴ> 하지만 여기서 바로 짝이 맞았다고 끝이 아니라 반례를 한 번더 생각해줘야 합니다. 
ㄴ> EX : ( ] ) 이런 경우 지금까지 설계한 조건에 모두 만족하지만 괄호 내부에 균형이 잡혀있지 않습니다.
ㄴ> 따라서 하나의 조건을 더 설정하여 pop을 할 수 있는지 아니면 이미 균형이 깨졌는지 확인해야합니다.

        2-1) if(스택이 비었거나 || 스택의 상단에 '('가 없다면)
        ㄴ> pop조건을 달성하기 위해서는 다른 것은 볼 필요 없이 스택의 top에 뭐가 있는지만 봅니다. 
        ㄴ> 균형이 깨졌으니 no를 출력하고 종료
        2-2) else 
        ㄴ> 위의 경우의 수에 해당되지 않는다면 스택이 비어있지 않고,

              top에 짝을 이룰 수 있는 왼쪽 괄호가 있다는 뜻입니다. 
        ㄴ> pop

3) else if(문자 == ']')

ㄴ> 나머지 조건은 위의 2번과 동일합니다. 괄호 두개를 구분한다고 했으니 조건을 나누어서 설정했습니다. 

package Stack;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class _4949 {
    public static String Balance(String msg) {
        Stack<Character> st = new Stack<Character>();
        
        for(int i=0; i<msg.length();i++) {
            char c = msg.charAt(i);
            
            if(c=='(' || c=='[') {
                st.push(c);
            }
            
            //여는 괄호가 아니라면 문자이거나, 공백이거나, 닫는 괄호. 닫는 괄호에 대한 조건만 생각
            else if(c==')') {
                //짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.//짝을 이룰 수 있는 오른쪽 괄호가 입력되었을때는 //반드시 스택의 최상단(가장 최근에 push된)에는 짝이 맞는 왼쪽괄호가 있어야 한다.
                if(st.empty() || st.peek() != '(') {
                    return "no";
                }else {
                    st.pop();
                }
            }
            
            else if(c==']') {
                if(st.empty() || st.peek() != '[') {
                    return "no";
                }else {
                    st.pop();
                }
            }
        
        }
        if(st.empty()) {
            return "yes";
        }else {
            return "no";
        }
 
    }
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        String msg;
        
        while(true) {
            msg = br.readLine();
            
            if(msg.equals(".")) 
                break;
            
            sb.append(Balance(msg)).append(" ");
        }
        System.out.println(sb);
    }
 
    
 
}