[LeetCode] 20번 - Valid Parentheses [Swift]

문제 링크

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.

 

Example 1:

Input: s = "()" Output: true

Example 2:

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

Example 3:

Input: s = "(]" Output: false

Example 4:

Input: s = "([)]" Output: false

Example 5:

Input: s = "{[]}" Output: true

 

Constraints:

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

문제 풀이

이 문제는 주어진 문자열의 괄호들이 올바르게 사용 중인지를 확인하는 문제였습니다.

이 문제의 포인트는 괄호의 종류가 3가지라는 것이라고 생각해요.

 

괄호 문제에서 중요하다고 느낀 것은 괄호를 여는 것 보다 닫는 게 중요하다는 것입니다.

괄호를 여는 것은 언제든지 열어도 됩니다.

하지만 닫을 때는 모양이 맞는 열린 괄호가 있고 그 괄호의 위치가 올바른 위치여야 하는 것이죠!

올바른 위치임을 확인하기 위해서 저는 stack을 사용했습니다.

위와 같이 스택을 사용했어요.

여는 괄호는 스택에 무조건 넣고 닫는 괄호가 나올 때 스택에서 꺼낸 괄호와 비교하여 모양이 맞으면 넘어가고 다르다면 false를 반환하여 불가능한 괄호임을 나타내 주시면 됩니다.

하지만 이러한 조건만 가지고는 위 문제의 답을 구할 수는 없어요.

모든 문자열을 확인한 뒤에 스택에 남은 문자가 있는지 확인해줘야 합니다.

만약 이때 남은 문자가 없다면 true, 문자가 있다면 false를 반환해줘야 하죠.

이유는 "(("와 같은 여는 괄호만 있을 경우 때문에 그렇습니다.

 

문제에서 조건으로 문자열의 길이가 1 이상 10000 미만이었기 때문에 문자열의 길이가 홀수가 나올 수도 있어요.

따라서 코드 시작점에 문자열의 길이를 확인해주고 홀수라면 그냥 false라고 해주는 코드를 넣으면 효율적인 코드가 될 수 있답니다.

소스 코드

class Solution {
    func isValid(_ s: String) -> Bool {
        
        if s.count % 2 == 1 {
            return false
        }
        
        var stack: [Character] = []
        
        for char in s {
            switch char {
            case "(":
                stack.append(char)
            case "{":
                stack.append(char)
            case "[":
                stack.append(char)
            case ")":
                if stack.popLast() == "(" {
                    continue
                } else {
                    return false
                }
            case "}":
                if stack.popLast() == "{" {
                    continue
                } else {
                    return false
                }
            case "]":
                if stack.popLast() == "[" {
                    continue
                } else {
                    return false
                }
            default:
                return false
            }
        }
        if stack.isEmpty {
            return true
        } else {
            return false
        }
    }
}