문제

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.

제한사항

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

접근

자료구조 수업 때가 생각나네요. 스택Stack을 활용해서 괄호가 올바르게 들어갔는지 확인하는 문제입니다.

1. 열린 괄호는 stack에 추가합니다.
2. 닫힌 괄호가 나오면 top의 괄호랑 매치가 되는지 확인해요.
3. 마지막으로 열린 괄호만 존재하는 경우, stack에 남아 있으므로 stack이 비었는지를 확인합니다.

답안

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stk = new Stack<>();

        for(int i = 0; i < s.length(); ++i){
            char character = s.charAt(i);
            switch (character){
                case '(':
                case '{':
                case '[':
                {
                    stk.push(character);
                } break;
                case ')':
                    if(stk.empty() || stk.peek() != '(') return false;
                    else stk.pop();
                    break;
                case '}':
                    if(stk.empty() || stk.peek() != '{') return false;
                    else stk.pop();
                    break;
                case ']':
                    if(stk.empty() || stk.peek() != '[') return false;
                    else stk.pop();
                    break;
            }
        }
        return stk.empty();
    }
}