[LeetCode] 20. Valid Parentheses (java)

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

 

 

문제 파악

오직 '(', ')', '{', '}', '[', ']' 만 포함된 문자열 s가 주어졌을 때, 해당 문자열이 유효한지 여부를 retur하기

 

 

문제 풀이

Stack

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 != 0)
            return false;

        Deque<Character> stack = new ArrayDeque<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {  // 여는 괄호
                stack.push(c);
            }
            else {  // 닫는 괄호
                if (stack.isEmpty()) { 
                    return false;
                }
                else {
                    char topC = stack.pop();
                    if ((c == ')' && topC == '(') || (c == '}' && topC == '{') || (c == ']' && topC == '['))
                        continue;
                    else 
                        return false;
                }
            }
        }
        
        if (stack.isEmpty()) 
            return true;
        else 
            return false;
    }
}

 

📊 실행 결과

• 최악의 경우 시간 복잡도: O(n)

 

 

Note

• for-each문을 사용하여 String을 순회하려면 toCharArray()를 사용하여 문자 배열(char[])로 변환해야 한다.
• 과거의 데이터를 임시로 저장해 두었다가, 최근 데이터부터 확인 및 삭제할 필요가 있을 때 👉 Stack 자료구조로 데이터 관리