[LeetCode] 20. Valid Parentheses - 문제풀이

Description

주어진 문자열에서 에서 괄호가 순서대로 닫혔는지 여부를 확인하여 반환하는 문제입니다.

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Constraints:

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

Solution 1. 스택(Stack)

public boolean isValid(String s) {
    if(s.length() % 2 != 0){return false;}
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        switch(c){
            case '(' : stack.push(')'); break;
            case '{' : stack.push('}'); break;
            case '[' : stack.push(']'); break;
            default :
                if(stack.isEmpty() || c != stack.pop())
                    return false;
        }
    }
    return stack.isEmpty()? true  : false;
}

괄호는 가장 먼저 동일한 괄호가 닫혀야 하므로 열린괄호가 나왔을때 스택에 닫힌 괄호를 넣어주고 닫힌 괄호가 나왔을때 가장 나중에 열린 괄호(스택에 가장 마지막에 들어간) 데이터를 pop하여 같은지 확인해 줍니다. 모든 문자열을 확인 했을때 stack이 비어있으면 true, 아니면 false를 반환합니다.

Reference

Valid Parentheses - LeetCode