[Leetcode(릿코드)] 20. Valid Parentheses (Easy)

leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

---

문제

괄호가 주어진다

1. 같은 타입의 괄호로 닫혀야만 한다

2. 올바른 순서로 닫혀야만 한다

 

예를 들면, 아래와 같다 

Example 1:

Input: s = "()" Output: true

Example 2:

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

Example 3:

Input: s = "(]" Output: false

Example 4:

Input: s = "([)]" Output: false

Example 5:

Input: s = "{[]}" Output: true

 

해결

map에 닫힌 괄호를 key, 열린 괄호를 value로 넣어둔다

그리고 set 2개를 만들어서 열린 괄호와 닫힌 괄호를 넣어둔다

주어진 괄호들을 char[]로 바꾼 후,

열린 괄호이면 스택에 넣는다

그리고 닫힌 괄호가 나오면 map을 통해 상응하는 열린 괄호를 꺼낸다

그리고 스택에서 하나 꺼내어 비교한다

최종적으로

스택이 비어있으면 true 아니면 false,

문자열을 비교하다가 중간에 스택이 비어버리면 false,

스택에서 꺼낸 값과 일치하지 않으면 false

public class ValidParentheses {

    public static void main(String[] args) {
        isValid("([]){");
    }

    public static boolean isValid(String s) {
        boolean result = false;
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        Stack<Character> open_stack = new Stack<>();
        Set<Character> open_set = new HashSet<>();
        open_set.addAll(Set.of('(','[','{'));
        Set<Character> close_set = new HashSet<>();
        close_set.addAll(Set.of(')',']','}'));

        for (char c  : s.toCharArray()) {
            if (open_set.contains(c)) {
                open_stack.push(c);
            } else if (close_set.contains(c)) {
                char close_c = map.get(c);
                if (open_stack.isEmpty()) {
                    result = false;
                } else {
                    result =  close_c == open_stack.pop() ? true : false;
                }
                if (!result) break;
            }
        }

        result = open_stack.isEmpty() ? result : false;
        return result;
    }
}