지금 바로 떠나자 먹으러....

문제:

주어진 문자열이 유효한 괄호인지 검사하는 함수를 작성하라.

괄호의 종류는 다음 세 가지가 있다. "( )", "{ }", "[ ]"

각 괄호의 우선순위는 존재하지 않지만 다른 괄호가 열려있는 중간에 닫는 괄호가 온다면 유효하지 않는 문자열이 된다.

예를 들어 "( [ ] )" 이 문자열은 유효한 것이다. 하지만 "( [ ) ]" 이 것은 유효하지 않은 문자열이다.

풀이:

이번 문제는 스택을 이용하면 간단히 해결 가능한 문제이다.

괄호 문자 중 여는 괄호가 나오면 스택에 push를 하고 닫힌 괄호가 나올 때 스택에서 pop을 해서 

두 쌍이 유효한 것 인지 비교한다.

두 쌍이 제대로 이뤄져 있다면 true

두 쌍이 서로 다른 괄호의 종류이거나 스택에 더이상 괄호가 없는데 pop을 시도한 경우는 false를 리턴한다.

또한 더이상 닫힌 괄호가 없는데 스택에 아직 데이터가 존재한다면 역시 false를 리턴한다.

Java code:

class Solution {
    public boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int top = 0;
        
        char [] temp = s.toCharArray();
        
        for(char c : temp) {
            if(c == '(' || c == '[' || c == '{') {
                stack[top++] = c;
            }
            else {
                if(top == 0){
                    return false;
                }
                
                char stored = stack[--top];
                switch(stored) {
                    case '(':
                        if(c != ')') return false;
                        break;
                    case '[':
                        if(c != ']') return false;
                        break;
                    case '{':
                        if(c != '}') return false;
                        break;
                }
            }
        }
        
        if(top != 0 ) return false;
    
        return true;
    }
}

Java의 Stack클래스를 사용해도 되지만 수행 성능을 위해서 char 배열을 대신 사용했다.