[stack] valid parentheses

✅ Problem

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

 

✅ Approach & Solution

방식1) stack, map 사용

class Solution {
    public boolean isValid(String s) {
    	// 유효성 검증을 위한 스택 선언
        Deque<Character> stack = new ArrayDeque<>();

        // 매핑 테이블 선언
        Map<Character, Character> table = new HashMap<>(){{
            put(')', '(');
            put('}', '{');
            put(']', '[');
        }};

        // 한 문자씩 처리
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 열림 괄호일 때
            if (!table.containsKey(c)) {
                stack.push(c);
            }
            // 닫힘 괄호일 때
            else if (stack.isEmpty() || table.get(c) != stack.pop()) {
                return false;
            }
        }

        // 문자열 순회 완료 후 빈 스택이어야 함
        return stack.isEmpty();
    }
}

 

방식2) 배열 사용

• char[]의 시작 idx = -1
• 열림 괄호일 때 대응하는 닫힘 괄호를 배열에 저장
• 닫힘 괄호일 때 배열의 마지막 원소가 본인과 일치하는지 확인 

class Solution {
    public boolean isValid(String s) {
        int idx = -1;
        char[] bracketArr = new char[s.length()];

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {
                bracketArr[++idx] = ')';
            } else if (c == '{') {
                bracketArr[++idx] = '}';
            } else if (c == '[') {
                bracketArr[++idx] = ']';
            } else {
                if (idx == -1 || bracketArr[idx--] != c) {
                    return false;
                }
            }
        }
        
        return idx == -1; // 문자열 모두 순회 후 빈 배열이어야 함
    }
}