Stack을 이용한 괄호 짝 맞추기 알고리즘 문제풀이

public static void main(String[] args) {
    System.out.println(solution("(){}[]"));             //true 
    System.out.println(solution("{(})}){)}{(}{)})("));  //false
    System.out.println(solution("{([])}"));             //true
    System.out.println(solution("{[}]"));               //false
    
}

괄호 (), {}, [] 세가지를 이용하여 괄호가 알맞게 열리고 닫혔는지 판단하는 solution 함수를 작성하시오. 즉, 위 main 메소드의 결과를 만족하는 solution 함수를 작성하시오.

 

풀이

private static boolean solution(String s) {
        if(s.length()%2 != 0) return false;
        Stack<Character> stack = new Stack<Character>();
        for(int i =0; i<s.length(); i++) {
            switch(s.charAt(i)) {
                //닫힌것은 비교하여 뺀다
                case ')':
                    if(stack.peek() == '(') stack.pop();
                    break;
                case '}':
                    if(stack.peek() == '{') stack.pop();
                    break;
                case ']':
                    if(stack.peek() == '[') stack.pop();
                    break;
                //열린것은 담고
                default :
                    stack.push(s.charAt(i));
                    break;
            }
        }
        return stack.empty();
    }

스택은 후입선출(Last In First Out) 구조입니다. 즉, IDE가 괄호를 판단할 때, Stack 의 구조를 이용하여 판단하게 될것입니다. 

 

이러한 괄호 짝맞추기 문제를 풀때는 "열린것은 stack에 담고, 닫힌것은 비교하여 뺀다." 이것만 기억하면 됩니다.

 

왜냐하면 알맞은 괄호는 무조건 열렸다가 닫은 것이고, 스택의 구조를 최대한 활용하기 위해서는 이 방법이 가장 유용합니다.

 

"{ [ } ]" 이 예제로 예를 들면, 처음 Stack 에는 "{"가 들어옵니다. 열렸으니까요. 

 

그다음 "[" 가 들어옵니다. 마찬가지로 열렸으니까요

 

그다음 "}" 가 들어왔습니다. 비교하여 빼야합니다. solution 함수의 다음부분에 걸리겠네요.

case '}':
    if(stack.peek() == '{') stack.pop();

stack의 peek를 보니 "[" 입니다. 조건에 만족하지 않고 for문을 탈출합니다. 아직 제 짝을 못만났거니 생각해봅시다.

 

그다음 "]" 가 들어왔습니다. solution 함수의 다음부분에 걸릴것입니다.

case ']':
    if(stack.peek() == '[') stack.pop();

조건에 만족하므로 스택에서 pop 연산을 해줍니다.

 

이제 모든 괄호를 소비하였고, 스택을 보니 아직 1개의 문자가 남았습니다. 제대로된 괄호기준을 맞췄다면 모두 소비되었을 텐데 마지막까지 stack에 값이 남아있게 되죠.

 

이런식으로 stack 구조에서 괄호순서를 대입하면 stack size가 0이되게 됩니다. 하지만 stack.empty() / false 가 나오게 된다면 올바르지 못한 괄호순서였다는 겁니다.

 

Stack으로 괄호문제를 접할때는 반드시!!

열린건 담고, 닫힌건 비교해서 뺀다.