[LeetCode/Kotlin]Easy - 20. Valid Parentheses

Valid Parentheses - LeetCode

문제

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. 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 <= 104
• s consists of parentheses only '()[]{}'.

풀이

나의 최종 풀이

풀이 접근 과정

처음엔 그냥 퐁당퐁당인 줄 알고 문제를 풀었다. 먼저 ‘(’ 가 왔으면 다음 글자는 ‘)’ 이게 나와야한다는 식으로 생각했다. 그런데 고려하지 못한 부분이 있었다. 퐁당퐁당이 아니라 ‘({})’ 이 경우에도 유효하다는 것이었다…. 그래서 Stack을 사용했다. string을 차근차근 Stack에 담고 비교하는 방법으로 진행했다.

최종 소스코드

괄호 문자열은 여는 괄호와 닫는 괄호가 쌍으로 이루어져야 하며, 괄호의 순서도 맞아야 합니다. 예를 들어, ()는 올바른 괄호 문자열이지만, (]와 ([)]는 올바른 괄호 문자열이 아닙니다.

이 함수는 문자열 s를 매개변수로 받아, 주어진 문자열이 올바른 괄호 문자열인지 검사합니다. 검사 결과에 따라 true 또는 false 값을 반환합니다.

함수 내부에서는 Stack<String>() 객체를 생성하여 스택을 구현하고, 주어진 문자열 s를 문자 단위로 순회하면서 스택에 괄호를 추가(add())하거나 스택에서 괄호를 제거(pop())합니다.

괄호를 제거할 때는, 스택에서 제거한 괄호와 주어진 문자열에서 읽은 괄호가 쌍으로 맞는지 확인합니다. 쌍으로 맞지 않는 경우 isTrue 변수에 false 값을 할당하고, 검사를 종료합니다. 검사 종료 후, 스택이 비어있지 않은 경우에도 올바른 괄호 문자열이 아니므로, false 값을 반환합니다.

마지막으로, isTrue 변수의 값을 반환합니다.

시간 복잡도는 O(n)입니다. 이유는 문자열 s를 한 번 순회하면서 각 문자를 처리하기 때문입니다. 각 문자를 처리할 때마다 스택에 push 또는 pop 연산을 수행합니다. 모든 연산은 상수 시간에 수행되기 때문에, 스택 연산의 시간 복잡도는 O(1)입니다. 따라서, 문자열의 길이를 n이라고 할 때, 총 시간 복잡도는 O(n)이 됩니다.

class Solution {
    fun isValid(s: String): Boolean {
        var isTrue = true
        val stack = Stack<String>()

        if (s.length%2 != 0) return false
        
        run {
            s.toCharArray().forEach {
                val now = it.toString()
                
                if (now == "(" || now == "{" || now == "[" || stack.isEmpty()) stack.add(now)
                else {
                    isTrue = when (stack.pop()) {
                        "(" -> now.equals(")")
                        "{" -> now.equals("}")
                        "[" -> now.equals("]")
                        else -> false
                    }
                }

                if (!isTrue) return@run
            }
        }

        if (stack.isNotEmpty()) return false

        return isTrue
    }
}

다른 사람의 풀이

풀이1

class Solution {
    fun isValid(s: String): Boolean {
        val stack = Stack<Char>()
        
        for (c in s) {
            when (c) {
                '(', '{', '[' -> stack.push(c)
                ')' -> if (stack.isEmpty() || stack.pop() != '(') return false
                '}' -> if (stack.isEmpty() || stack.pop() != '{') return false
                ']' -> if (stack.isEmpty() || stack.pop() != '[') return false
            }
        }
        
        return stack.isEmpty()
    }
}

스택 자료구조를 사용하여 괄호의 짝이 맞는지를 검사하는 방법은 간단합니다. 왼쪽 괄호는 스택에 넣어주고, 오른쪽 괄호를 만나면 스택에서 가장 위의 괄호와 짝이 맞는지 검사합니다. 짝이 맞지 않으면 바로 false를 반환합니다. 마지막으로 모든 문자열을 검사한 후에 스택이 비어있는지 확인하여, 비어있다면 true를 반환합니다.

시간복잡도는 제 풀이법과 같습니다.

똑같이 stack을 사용했는데 이렇게 깔끔하게 작성할 수 있었다니 …ㅠㅠ

풀이2

class Solution {
    fun isValid(s: String): Boolean {
        if (s.isEmpty()) return true
        val simplify = s.replace("()", "").replace("{}", "").replace("[]", "")
        if (simplify == s) return false
        return isValid(simplify)
    }
}

해당 함수는 재귀적인 접근 방식을 사용하여 유효한 쌍을 제거할 수 없을 때까지 문자열을 단순화합니다. 단순화된 문자열이 비어있다면, 모든 쌍이 제거되어 원래 문자열이 유효하다는 의미입니다. 만약 단순화된 문자열이 원래 문자열과 같다면, 더 이상 제거할 쌍이 없다는 의미로 문자열이 유효하지 않습니다.

그러나 주의할 점은 코드가 (), {}, []와 같은 특정 문자만 처리하며 다른 문자 조합을 처리하지 않는다는 점입니다. 더 복잡한 시나리오의 경우, 스택 기반 접근 방식이 더 적합할 수 있습니다.

시간 복잡도는 주어진 코드의 경우 O(n^2)입니다. 각 단계에서 replace 함수를 사용하여 문자열에서 유효한 쌍을 제거하기 때문에 문자열의 길이에 비례하는 시간이 소요됩니다. 최악의 경우, 모든 문자열에서 유효한 쌍을 제거할 때까지 반복하기 때문에 n번 반복됩니다. 따라서, 문자열의 길이를 n이라고 할 때, 총 시간 복잡도는 O(n^2)입니다.

Comment

처음으로 IDE 없이 풀었더니 오류가 많이 났고, 디버깅을 해보기 힘들어서 헤맸다.