본문 바로가기
Algorithm/Leetcode

LeetCode - Valid Parentheses

by du.it.ddu 2020. 6. 27.
반응형

문제 링크 : https://leetcode.com/problems/valid-parentheses/

난이도 : Easy


문제 풀이 :

자주 접하는 괄호 짝 맞추기 문제다.

스택을 사용하면 어렵지 않게 풀 수 있다.

여는 괄호인 (, [, { 가 나오면 스택에 담고, 닫는 괄호인 ), ], } 가 나오면 스택의 Top에 있는 것을 빼내어 짝이 맞는지 검사한다.

Top에 쌓인 것이 없거나, 무사히 for-loop를 빠져나왔더라도 마지막에 스택이 비어있지 않을 수 있다. 이 부분만 잘 고려하면 어렵지 않게 풀 수 있따.


소스 코드 :

class ValidParentheses {
    fun isValid(s: String): Boolean {
        val stack = Stack<Char>()

        for(bracket in s) {
            if (bracket == '(' || bracket == '[' || bracket == '{') {
                stack.add(bracket)
            } else {
                if(stack.isEmpty()) {
                    return false
                } else {
                    val pair = getPairOfBracket(bracket)
                    val prev = stack.pop()

                    if (pair != prev) {
                        return false
                    }
                }
            }
        }
        return stack.isEmpty()
    }

    private fun getPairOfBracket(bracket: Char) = when(bracket) {
        ')' -> '('
        ']' -> '['
        '}' -> '{'
        else -> ""
    }
}

후기 : 

이 문제는 풀다보면 괄호 짝 검사를 위한 if문이 많이 발생한다.

이게 싫어서 괄호 짝을 HashMap에 담아서 풀었었다. 하지만 이게 공간 복잡도를 높이는 원인이 되었고 함수로 분리하는 방법으로 변경했다.

문제를 풀면서 좀 더 깔끔한 코드를 짜려고 노력한 스스로가 살짝 기특했다(?)

반응형

'Algorithm > Leetcode' 카테고리의 다른 글

LeetCode - Remove Duplicates from Sorted Array  (0) 2020.08.02
LeetCode - Merge Two Sorted Lists  (0) 2020.07.30
LeetCode - Longest Common Prefix  (0) 2020.06.27
LeetCode - Roman to Integer  (0) 2020.06.27
LeetCode - Reverse Integer  (0) 2020.06.27