[Leetcode/Easy] 유효한 괄호 (20. Valid Parentheses, Swift)

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

 

🤔 문제 설명

괄호 '(', ')', '{', '}', '[', ']'로 되어있는 문자열이 주어지면 아래와 같은 규칙에 맞아 유효한지를 판단하라.

1. 열린 괄호는 동일한 유형의 괄호로 닫아야 한다. -> '(' 괄호인 경우, ')' 괄호로 닫아야 한다.
2. 열린 괄호는 올바른 순서로 닫아야 한다. -> '({' 괄호인 경우, '})' 괄호 순서대로 닫아야 한다.

 

💡 풀이

스택(Stack) 자료형을 사용한다면 풀 수 있는 문제였다.

문자열을 하나씩 반복하면서 볼 수 있는 경우는 크게 두 가지. 열린 괄호가 오는 경우와 닫힌 경우가 오는 경우이다.

열린 괄호가 오는 경우에는 스택에 push해준다.
닫힌 괄호가 오는 경우에는 스택에 있는 문자를 pop해서 열린 괄호 쌍이 맞는지 비교를 해주면 된다. (위의 1번 규칙에 의해)

만약 스택에서 pop을 하려고 했는데 스택이 비어있는 경우? -> 열린 괄호가 없는데 닫힌 괄호가 먼저 온 경우니 유효할 수가 없다.
스택에서 pop한 문자와 닫힌 괄호가 일치하지 않는 경우? -> 2번 규칙에 의해 올바른 규칙이 아니니 유효할 수가 없다.
모든 문자를 다 돌았는데 스택에 열린 괄호가 남아있는 경우? -> 아직 열린 괄호에 비해 닫힌 괄호가 안 온 경우니 유효할 수가 없다.

 

🧑🏻‍💻 코드 (Swift ver.)

💡 Runtime : 5ms (Beats 49.32%), Memory : 16.90MB (Beats 8.65%)

class Solution {
    func isValid(_ s: String) -> Bool {
        let dict = ["(": ")", "{": "}", "[": "]"]
        var stack = [String]()

        for check in s {
            if (check == "(" || check == "{" || check == "[") {
                stack.append(String(check))
            }
            if (check == ")" || check == "}" || check == "]") {
                // false 상황 1. 닫힌 괄호가 왔는데 앞에 열린 괄호가 없었던 경우
                guard let last = stack.popLast() else { return false }  

                // false 상황 2. 닫힌 괄호가 앞 열린 괄호와 매칭이 안될 경우
                if let compare = dict[last], compare != String(check) { return false }
            }
        }

        return stack.isEmpty
    }
}