Valid Parentheses

문제

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

---

풀이

이번의 괄호 문제는 소괄호 뿐만 아니라 중괄호, 대괄호까지 포함하는 문제이다.
(){}[]가 담긴 문자열에서 해당 괄호가 올바른지를 확인하자.

1. 열린 괄호 ( { ]를 만나면 Stack에 넣는다.
2. 닫힌 괄호 ) } ]를 만나면 Stack에 있는 열린 괄호를 pop하여 닫힌 괄호의 짝이 맞는지를 확인한다.
3. 만약 짝이 맞지 않는다면 올바르지 않은 괄호이다.
4. 만약 모든 문자를 확인했는데, Stack이비어있지 않다면 올바르지 않은 괄호이다.

import java.util.*;


class Solution {
    public boolean isValid(String s) {
    // ()=1, {}=2, []=3
        Stack<Integer> st = new Stack<>();

        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (c=='(') st.push(1);
            else if (c=='{') st.push(2);
            else if (c=='[') st.push(3);
            else {
                if (!st.isEmpty()) {
                    int close = st.pop();
                    if (c==')' && close != 1) return false;
                    else if (c == '}' && close != 2 ) return false;
                    else if (c==']' && close != 3) return false;
                } else return false;
            }
        }
        if (!st.isEmpty()) return false;
        return true;
    }
}

2ms

---

Stack을 사용하지 않고

배열만으로도 해당 문제를 풀 수 있다.
열린 괄호를 만나면 그에 해당하는 닫힌 괄호를 배열에 차곡차곡 넣으면서,
닫힌 배열을 만났을 때 제일 마지막에 있는 괄호와 일치하는 지 확인하는 것이다.

만약 일치하지 않으면 열린 괄호와 닫힌 괄호의 짝인 맞지 않는 상태이다.

즉, 배열로 Stack을 구현하는 것이긴 하지만, 래퍼 클래스(박싱 타입)을 사용하지 않고 기본형인 char로 해결할 수 있으며 인덱스만을 사용한다.

import java.util.*;


class Solution {
    public boolean isValid(String s) {
        char [] stack = new char[s.length()];
        int index = -1;
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(' -> stack[++index] = ')';
                case '{' -> stack[++index] = '}';
                case '[' -> stack[++index] = ']';
                default -> {
                    if (index == -1 || stack[index] != c) return false;
                    index--;
                }
            }
        }
        if (index != -1) return false;
        return true;
    }
}

0ms

아무래도 박싱, 언박싱 하는 과정에서 시간이 걸린 것 같았다. 해당 과정을 없애니 빠르게 처리가 되었다!