[LeetCode] - 20. Valid Parentheses

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Valid Parentheses" 문제입니다.

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

 

문제 : 

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if : Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Every close bracket has a corresponding open bracket of the same type.

---

Example 1 :

Input : s = "()"

Output : true

 

Example 2 :

Input : s = "()[]{}"

Output : true

 

Example 3 :

Input : s = "(]"

Output : false

 

Constraints :

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

---

이 문제는 주어진 문자열 s는 '(', ')', '{', '}', '[', ']' 문자로만 구성됩니다. 문자열이 유효하려면 모든 여는 괄호가 같은 유형의 닫는 괄호로 닫혀야 하며, 올바른 순서로 닫혀야 합니다. 예를 들어, 입력이 "()" 또는 "()[]{}"인 경우 출력은 true이고, "(]"인 경우 출력은 false입니다.

코드를 보시겠습니다 : 

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(')');
            } else if (s.charAt(i) == '{') {
                stack.push('}');
            } else if (s.charAt(i) == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != s.charAt(i)) {
                return false;
            }
        }

        return stack.isEmpty();
    }
}

 

저는 우선, 알고리즘 수업 때 풀었던 문제가 생각나서 비슷하게 풀어봤습니다. 바로, 스택을 활용하는 것입니다. 제 코드를 좀 더 상세하게 설명드리자면 : 

1. 스택 초기화:
   • 여는 괄호를 저장하기 위한 스택을 초기화합니다.
2. 문자열 순회:
   • 문자열의 각 문자를 순회합니다.
   • 여는 괄호인 경우, 스택에 대응하는 닫는 괄호를 푸시합니다.
   • 닫는 괄호인 경우, 스택이 비어 있거나, 스택에서 꺼낸 값이 현재 닫는 괄호와 일치하지 않으면 false를 반환합니다.
3. 결과 반환:
   • 문자열을 모두 순회한 후 스택이 비어 있으면 true를 반환합니다. 비어 있지 않으면 false를 반환합니다.

시간 및 공간 복잡도 분석:

1. 시간 복잡도:
   • 문자열의 각 문자를 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다.
2. 공간 복잡도:
   • 스택에 저장되는 여는 괄호의 수는 최악의 경우 문자열의 길이 n과 같을 수 있으므로 공간 복잡도는 O(n)입니다.

요약:

이 코드는 여는 괄호를 스택에 저장하고, 닫는 괄호를 만날 때마다 스택에서 꺼내어 유효성을 확인하는 방식으로 동작합니다. 유효한 괄호 문자열인지 검사하는 효율적인 방법이며, 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.

---

코드의 Runtime 결과