[LeetCode][Stack] 20. Vali Parentheses

 

 

 

 

문제 링크

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

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.

 

 

 

문제 해석

 

문제를 풀다보면 parentheses 문제도 한번쯤은 접하게 될 것!

그 중 정말 정말 기본적인 문제라고 할 수 있는 EASY 문제이다.

 

풀이도 정말 간단하다.

• 열린 괄호이면 stack push!
• 닫힌 괄호이면 stack pop! → 짝이 맞는지 검사!

 

여기서 중요한건 stack size를 검사해 줘야 한다는 것이다.

이 부분이 이 문제의 edge case라고 할 수 있다.

즉, s = "([]" 또는 s = "[])" 와 같이 양 쪽의 개수가 맞지 않는 문자열이 들어올 경우를 체크해 주어야 하는 것.

(사실 이건 껌이지 하고 우쭐대다가 FAIL 을 만났다 {{{(>_<)}}} )

 

코드 주석에 표시해 두었다!

 

 

 

제출 코드

class Solution {
    
    private boolean isOpen(char c) {
        if (c == '(' || c == '{' || c == '[') return true;
        else return false;
    }
    
    private boolean isMatch(char a, char b) {
        if ((a == '(' && b == ')')
            || (a == '{' && b == '}')
            || (a == '[' && b == ']')) return true;
        else return false;
    }
    
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] charArr = s.toCharArray();
        
        for (char c : charArr) {
            if (isOpen(c)) stack.push(c);
            else {
                if (stack.size() == 0) return false; // here! case s="[])"
                
                char popItem = stack.pop();
                if (!isMatch(popItem, c)) return false;
            }
        }
        
        if (stack.size() == 0) return true; // here! case s="([]"
        else return false;
        
    }
}

 

 

 

제출 결과

 

 

 

 

 

 

 

 

 

우쭐대지말자!

{{{(>_<)}}}

 

- mushroong

 

 

 

 

---