[LeetCode] Valid Parentheses

문제

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

Example 4:
Input: s = "([])"
Output: true

Constraints:
- 1 <= s.length <= 10⁴
- s consists of parentheses only '()[]{}'.

고민

괄호의 짝꿍이 없으면 false, 짝꿍이 다 있다면 true 인 문제이다.
예시로만 봤을 때에는 '(', '[', '{' 를 key 값으로 잡고 value 를 닫힌 괄호로 해서 루프를 돌며 확인하면 되보인다.
하지만 언제나 이렇게 쉽진 않겠지..ㅎ

아무리 생각해도 map 말고는 방법이 없어보인다. 한번 해보자.

해결

class Solution {
    fun isValid(s: String): Boolean {
        val tempStack = Stack<Char>()
        val bracketMap = mapOf(
            ')' to '(',
            ']' to '[',
            '}' to '{'
        )
        for (char in s) {
            if (char in bracketMap.values) {
                tempStack.push(char)
            } else {
                if (tempStack.isEmpty() || tempStack.removeLast() != bracketMap[char]) {
                    return false
                }
            }
        }
        return tempStack.isEmpty()
    }
}

solved 된 코드이다. 여기까지 오기에 많은 시행 착오가 있었다.

앞서 고민했던 것과 마찬가지로 키 값을 열린 괄호로 해서 처리하니 많은 테스트 케이스에서 fail 이 났었다.
닫힌 괄호로 시작될 수 도 있고, 닫힌 괄호만 있을 수도 있기 때문이다.
어찌어찌 고치고 또 고치고 한 결과물이 해당 코드이다.

지금까지 안드로이드 프로젝트를 진행하면서 `Stack`객체는 사용해본적이 없다. (내가 많이 부족해서, 활용 방법이 익숙치 않아서 그런거겠지만..ㅎ)
일단, map 으로 정리를 하는게 맞다. 하지만 key 값이 열린 괄호가 아니라 닫힌 괄호로 key 를 잡고, value 가 열린 괄호로 진행했다.

루프를 돌며 확인하는데 요소가 열린 괄호가 맞다면 stack 에 추가하고, 닫힌 괄호라면 조건을 검사한다.
stack 이 비어있다면 무조건 false 이다. 짝꿍이 없으니까.
stack의 최근 요소를 끄내와 for 문의 요소를 key 값으로 가지는 열린 괄호를 찾아 같지 않다면 false 를 반환한다.
(Stack 은 후입 선출이니까!)

'([)]' 를 예를 들어보자.
'('는 map 의 value 에 포함 되니 stack 에 쌓인다. '[' 도 마찬가지.
그 다음 요소인 ')'를 보자.
stack의 최근 요소인 '['가 bracketMap[")"] 은, '('니까 같지 않음으로 조건에 부합해서 false 를 반환하게 되는 것이다.

결과

후기

class Solution {
    fun isValid(s: String): Boolean {
        val len = s.length
        if (len % 2 != 0) return false
        val chars = CharArray(len / 2)
        var pos = -1

        for (char in s) {
            when (char) {
                '(', '{', '[' -> {
                    pos++
                    if (pos >= chars.size) return false
                    chars[pos] = char
                }

                ')' -> {
                    if (pos == -1 || '(' != chars[pos]) return false
                    pos--
                }

                '}' -> {
                    if (pos == -1 || '{' != chars[pos]) return false
                    pos--
                }

                ']' -> {
                    if (pos == -1 || '[' != chars[pos]) return false
                    pos--
                }
            }
        }

        return pos == -1
    }
}

0ms 걸린 코드이다.
저 아름다운 예외처리를 보라. 짝꿍들이 다 맞으려면 무조건 짝수여야 하는데 홀수인 경우 미리 false 를 반환하다니..
나는 `Stack`객체를 사용했지만 이 사람은 CharArray로 사용했다. 또한 배열의 크기는 문자열 길의 절반. 아마도 한쪽 방향의 괄호만 담아서 짝꿍이 맞는지를 보는 목적이었을 것이다.
pos 라는 integer 변수가 있는데 해당 변수로 stack의 위치를 확인하는 용도인 것 같다.

이제 루프를 돌면서 첫번째 case 는 나와 동일한 방법으로 진행했다. 열린 괄호라면 stack 에 추가를 한다. 하지만 stack 의 위치를 pos 로 처리를 하였다.
근데 여기서도 예외를 처리한다. 열린 괄호가 배열의 크기보다 크게 된다면 이미 짝꿍이 맞지 않으니 false 를 반환한다.

이제 닫힌 괄호처리 케이스이다.
나의 `tempStack.isEmtpy()` 조건을 pos 가 -1 인지 아닌지 판단하거나, 현재 위치의 char 배열에서 열린 괄호와 짝꿍이 아니라면 false. 아니라면 stack 을 지우는게 아닌 위치인 pos 를 감소.
다른 괄호도 이러한 처리로하고 마지막 return 을 pos 가 -1 인지 아닌지로 반환한다.

결국 열린 괄호를 특정 공간에 저장 후 확인 하는 방법은 동일하지만 내가 Runtime 이 오래걸린 이유는 아마도 map 이라는 객체를 사용해서 그런 것같다는 생각이 든다.

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

5ms 를 줄였다. 될 수 있으면 객체 사용을 최소한으로 하는 습관을 들여야겠다.