괄호 검사 문제

괄호 검사 문제

조건
1. 모든 괄호(),{},[]가 짝을 이뤄야 한다.
2. 올바른 순서로 배치되어 있어야 한다. "{[()]}"(O), "([)]"(X)

시행착오(틀림)

브루트 포스

int big = 0;
int mid = 0;
int sma = 0;
for(int i = 0; i<arr.length; i++) {
    switch (arr[i]) {
        case '{':
            mid++;
            break;
        case '}':
            mid--;
            if(mid<0) return false;
            break;
...

예외 : "([)]" 이런 다른 괄호끼리 순서 바뀐 것들 판별 못함.

해결 방법 - 스택

문자열을 하나씩 읽으면서
1. 여는 괄호 -> 스택에 넣기
2. 닫는 괄호 -> 스택에서 pop한 값과 짝이 맞는지 검사
3. 모두 검사한 후 스택이 비어있는지도 확인

코드

static boolean check(char[] arr) {

    Stack<Character> stack = new Stack<>();

    for(int i = 0;i<arr.length;i++) {
        char c = arr[i];
        if (c == '(' || c == '{' || c == '[') {
            stack.add(c);
        } else {
            if(stack.isEmpty()) return false;
            char o = stack.pop();
            if(!((o == '(' && c == ')') || 
                (o == '{' && c == '}') || 
                (o == '[' && c == ']'))) return false;
        }
    }

    if(stack.isEmpty()) {
        return true;
    } else {
        return false;
    }
}