[알고리즘] Valid Parentheses

문제 정보

출처 : leetcode
난이도 : easy

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

[예제]
Input: s = "()[]{}"
Output: true

내풀이

괄호 중 여는 괄호인 '(', '{', '['는 stack에 넣어주고 닫는 괄호가 나오면 stack에서 pop을 해서 여는 괄호를 하나씩 지워준다.
시간복잡도 : O(n)
공간복잡도 : O(n)

class Solution {
    private static Map<String, String> map = new HashMap<>();
    static {
        map.put(")", "(");
        map.put("}", "{");
        map.put("]", "[");

    }
    public boolean isValid(String s) {
        if ("".equals(s) || s.length() == 0) {
            return true;
        }

        Stack<String> st = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            String value = s.substring(i, i+1);
            
            if (map.containsValue(value)) {
                st.push(value);
            } else {
                if (st.isEmpty()) {
                    return false;
                }
                
                if (!st.pop().equals(map.get(value))) {
                    return false;
                }
            }
        }

        if (!st.isEmpty()) {
            return false;
        }

        return true;
    }
}

Runtime : 3 ms
Memory : 41 MB

개선하기

stack을 사용하는 건 맞았지만, 몇가지 수정사항이 있었다.
1. "".equals(s) 를 체크하는 건 어차피 for문에서 lenth가 0이면 안 돌기 때문에 필요 없었다.
2. 아래 부분은 그냥 return st.isEmpty()라고 하면 되는데 왜 이렇게 구현했는지 모르겠다. 아직 문제를 많이 풀어보지 않아서 성공에만 집중하다보니 기본적인 걸 놓쳤다.

		if (!st.isEmpty()) {
            return false;
        }

        return true;

3. 괄호는 () {} [] 두개씩 짝을 이루기때문에 s.length가 무조건 짝수여야한다. 맨위에 짝수 체크를 해서 홀수이면 false를 return 하였다.

시간복잡도 : O(n)
공간복잡도 : O(n)

class Solution {
    private static Map<Character, Character> map = new HashMap<>();
    static {
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');

    }
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }

        Stack<Character> st = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char value = s.charAt(i);

            if (map.containsValue(value)) {
                st.push(value);
                continue;
            }

            if (st.isEmpty() || st.pop() != map.get(value)) {
                return false;
            }

        }

        return st.isEmpty();
    }
}

Runtime : 2 ms
Memory : 40.8 MB

개선하여 runtime이 1초 줄었다.