본문 바로가기
코딩테스트/Leet Code

[LeetCode] 자바, 20. Valid Parentheses

by 핸디(Handy) 2020. 8. 10.

문제는 '들어온 괄호들이 짝을 제대로 이뤘느냐를 확인해줘라' 입니다.


첫번째.

class Solution {
    public boolean isValid(String s) {
        if (s.length() == 0)
            return true;
        if (s.length() % 2 != 0)
            return false;
        Stack<String> stack = new Stack<>();
        String[] arrayStr = s.split("");
        for (int i = 0; i < arrayStr.length; i++) {

            switch (arrayStr[i]) {
                case "(": {
                    stack.push("(");
                    break;
                }
                case "[": {
                    stack.push("[");
                    break;
                }
                case "{": {
                    stack.push("{");
                    break;
                }
                case ")": {
                    if (!stack.empty() && stack.peek().equals("(")) {
                        stack.pop();
                    } else {
                        return false;
                    }
                    break;
                }
                case "]": {
                    if (!stack.empty() && stack.peek().equals("[")) {
                        stack.pop();
                    } else {
                        return false;
                    }
                    break;
                }
                case "}": {
                    if (!stack.empty() && stack.peek().equals("{")) {
                        stack.pop();
                    } else {
                        return false;
                    }
                    break;
                }
            }
        }
        return stack.empty();
    }
}

아이디어는 '스택을 활용해서 풀어나가며 확인해서 있는 값이면 패스 없는데 pop요청이면 false를 하자 입니다.'

코드를 보시면 아주 개판으로 구현되어있는걸 확인하실수 있습니다. ㅜㅜ

두번째. hash map를 이용한 구현

class Solution {
    static Map<Character, Character> mappings = new HashMap<>();
    static {
        mappings.put('(', ')');
        mappings.put('[', ']');
        mappings.put('{', '}');
    }
    
    public boolean isValid(String s) {        
        Stack<Character> parenthesis = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (mappings.containsKey(c)) {
                parenthesis.push(mappings.get(c));
            } else if (mappings.containsValue(c)) {
                if (parenthesis.isEmpty() || parenthesis.pop() != c) {
                    return false;
                }
            }
        }
        return parenthesis.isEmpty();
    }
}

훨씬 개선되었습니다. 첫번째 시도에서 했던 알고리즘을 압축한 코드인데 속도는 더 빨라졌네여.

댓글