리트코드 - 20. Valid Parentheses

리트코드 - 20. Valid Parentheses

출처 - https://leetcode.com/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 문자열 s가 단순히 문자 '(', ')', '{', '}', '[', ']'만을 포함하고 있는 경우, 입력 문자열이 유효한지를 확인합니다.
유효한 입력 문자열의 조건은 다음과 같습니다:

1. 여는 괄호는 동일한 종류의 괄호로 닫혀야 합니다.
2. 여는 괄호는 올바른 순서로 닫혀야 합니다.
3. 각 닫는 괄호는 동일한 종류의 여는 괄호와 대응되어야 합니다.

의사코드

stack = new stack char[] arr = s를 char array로 변경 반복문 시작 (arr 배열 순회)     if (배열 값 == '(' or '{' or '[')         stack에 push     else         if (stack이 비었으면)             false 리턴         top = stack에서 peek         if ((배열값 == ')' 이면서 top != '(' ) or ((배열값 == '}' 이면서 top != '{' ) or ((배열값 == ']' 이면서 top != '[')              false 리턴         stack에서 pop  반복문 종료 stack.isEmpty 리턴

 

풀이코드

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] arr = s.toCharArray();

        for (char c : arr) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.peek();
                
                if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                    return false;
                }
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}

코드설명

스택을 이용하면 간단히 풀리는 문제다.

문자열을 char배열로 만들어서 한글자씩 순회하는데 여는 괄호를 만나면 스택에 넣고 닫는 괄호를 만나면 스택에서 엿본다.

짝이 맞지 않으면 false를 리턴하고 아니면 pop을 해서 하나 꺼낸다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

백준에서 풀어봤던 문젠데 그때보다는 빨리 푼 것 같다.

stack을 이용한 가장 기본적인 문제가 아닌가 싶다.

 

정리

stack 사용 아이디어 떠올리기