20180306 Valid Parentheses

Valid Parentheses

설명

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

풀이

스택을 이용해서 풀었다. 열린 괄호와 닫힌 괄호의 쌍을 맞추어주면 되기 때문에 그것만 유의해주면 풀 수 있었다. 

따로 자바 API에 내장된 스택 라이브러리를 쓰지 않고 직접 해당 Solution 클래스의 내부 클래스로 스택을 만들어서 풀어보았다.

Runtime : 12ms

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack();
        char openParenthness[] = {'(', '[', '{'};
        char closeParenthness[] = {')', ']', '}'};
        
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            
            for(int bIndex = 0; bIndex < 3; bIndex++){
                if(c == openParenthness[bIndex])
                    stack.push(c);
                if(c == closeParenthness[bIndex]){
                    if(stack.size() == 0)
                        return false;
                    
                    char openChar = stack.pop();
                    
                    if(!(openChar == '(' && c == ')' || openChar == '[' && c == ']' || openChar == '{' && c == '}'))
                        return false;
                }
            }
        }
        if(stack.size() >= 1)
            return false;
        
        return true;
    }
    
    class Stack{
        char[]array;
        int capacity;
        int size;
        
        Stack(){
            size = 0;
            capacity = 10;
            array = new char[capacity];
        }
        
        void push(char c){
            if(size < capacity){
                array[size++] = c;
                return;
            }
            
            // size >= 10
            resize();
            array[size++] = c;
        }
        
        void resize(){
            capacity = capacity + (capacity >> 1);
            array = Arrays.copyOf(array, capacity);
        }
        
        char pop(){
            if(size <= 0){
                System.out.println("배열 음수 값 반환");
                System.exit(1);
            }
            
            return array[--size];
        }
        
        int size(){
            return size;
        }
    }
}

Runtimes : 8ms

스택은 동일하게 구현했고 내부 내용을 약간 수정하였다.

public boolean isValid(String s) {
    Stack stack = new Stack();
    
    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        
        switch(c){
        // 열린 괄호
        case'(':
            stack.push(c);
            break;
        case'[':
            stack.push(c);
            break;
        case'{':
            stack.push(c);
            break;
        // 닫힌 괄호
        default:
            if(stack.size() <= 0) 
                return false;
            
            char anotherC = stack.pop();
            
            if(anotherC == '(' && c == ')') break;
            if(anotherC == '[' && c == ']') break;
            if(anotherC == '{' && c == '}') break;
            
            return false;
        }
    }
    
    if(stack.size() >= 1)
        return false;
    
    return true;
}