[백준 온라인저지]괄호 - 스택

괄호

이번 포스팅 문제는 9012번 입니다. 이번 문제 역시 스택을 이용하여 풀이하였습니다.

문제요약

주어진 문자열이 올바른 괄호인지 판단하는 문제입니다. 올바른 괄호란 여는 괄호, 닫는 괄호의 순서와 수량이 같은 괄호를 말합니다.

풀이전략

그럼 올바른 괄호를 판단하는 기준을 생각해보겠습니다. 

1. 여는 괄호와 닫는 괄호의 개수가 같아야 합니다.
2. 여는 괄호와 닫는 괄호의 순서가 올바라야 합니다
1. 닫는 괄호가 나왔을 때 이전 여는 괄호 중에서 가장 가까운 괄호와 매핑된다.
2. 닫는 괄호가 나왔을 때 이전 여는 괄호 중에서 매핑되지 않은 여는 괄호가 하나이상 존재해야 한다.

그럼 스택을 이용한 풀이 전략을 짜보도록 하겠습니다.

1. 주어진 문자열을 문자 배열로 변환합니다
2. 배열을 순회하며 여는 괄호라면 스택에 담고 닫는 괄호라면 스택의 내용을 추출한다. 
   이 때, 스택의 내용을 추출하려고 할 때 스택이 비어있다면 순서 또는 개수가 맞지 않으므로 올바른 괄호가 아님을 알 수 있습니다.
3. 배열을 모두 순회하였을 때 스택이 비어있다면 올바른 괄호이며 비어있지 않다면 개수가 맞지 않으므로 올바른 괄호가 아님을 알 수 있습니다.

구현하기

package BackJoon.스택;
 
import java.util.Scanner;
import java.util.Stack;
 
public class _9012_괄호 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        sc.nextLine();
        
        for(int i=0; i<T; i++) {
            String s = sc.nextLine();
            String solution = getSolution(s);
            System.out.println(solution);
        }
    }
    
    private static String getSolution(String s) {
        char[] charArr = s.toCharArray();
        
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<charArr.length; i++) {
            char c = charArr[i];
            // 여는 괄호라면 스택에 추가
            if(c == '(') {
                stack.push(c);
            } // 닫는 괄호라면 스택에서 꺼냄 
            else if(c == ')') {
                // 꺼낼 여는 괄호가 없다면 여는 괄호와 닫는 괄호 순서가 맞지않음
                if(stack.isEmpty()) {
                    return "NO";
                }
                stack.pop();
            }
        }
        // 스택이 비어있지않다면 여는 괄호와 닫는괄호 갯수가 맞지않음
        return stack.isEmpty() ? "YES" : "NO";
    }
}
 

배운점

스택을 사용한 가장 큰 이유는 "닫는 괄호가 나왔을 때 가장 가까운 여는 괄호와의 매핑" 이였습니다. 스택의 성질중 가장 마지막에 삽입한 원소가

가장 먼저 추출된다는 성질이 있기때문에 적합하다고 판단하였습니다.