[Easy] 20. Valid Parentheses

문제

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

An input string is valid if:

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

 

코드

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isValid(String s) {
        // 문자가 들어갈 스택 생성
        Deque<Character> stack = new ArrayDeque<>();

        // c에 한 글자씩 담음
        for(char c : s.toCharArray()) {

            // 1. 열린 괄호인지 판단
            if (c == '(' || c == '{' || c == '['){
                stack.push(c);
            }
            // 2. 닫힌 괄호인지 판단
            else if (c == ')' || c == '}' || c == ']') {
                // 2-1. 닫힌 괄호일 때 스택에서 꺼내와서 비교할 게 없으면 false 반환하고 끝
                if (stack.isEmpty()){
                    return false;
                }
                // 2-2. 스택에서 후입선출을 하기 위해서 마지막 글자 가져오기
                char lastOpen = stack.pop();

                // 2-3. 각 괄호에 맞게 닫히는지 검증
                if (c == ')' && lastOpen != '('){
                    return false;
                }
                if (c == '}' && lastOpen != '{'){
                    return false;
                }
                if (c == ']' && lastOpen != '['){
                    return false;
                }
            }
        }
        // 3. 다 끝나고 나서 스택에 남은 게 없는지 확인(남아 있을 경우 괄호 짝이 맞지 않음)
        return stack.isEmpty();
    }
}

 

풀이

• 후입선출인 Stack을 이용하여 풀기
• 한 글자씩 열린 괄호일 때는 스택에 push, 닫힌 괄호일 때는 pop 하여 비교
• 마지막으로 모두 소거됐는지 isEmpty()를 이용하여 체크

Github 링크

• LeetCode - Valid Parentheses(Easy)