[리트코드] 20. Valid Parentheses

리트코드 20번 문제.

난이도: Easy

 

문제

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.

괄호만으로 이루어진 string이 valid 한 지를 리턴하는 문제이다. list of bracket에서 opening bracket이 closing bracket과 매치되면 valid bracket이다

 

예시

Example 1

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

 

답

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        bracket_dict = {"{": "}", "[": "]", "(": ")"}

        for char in s:
            if char in ("{", "[", "("):
                stack.append(char)
            else:
                if not stack:
                    return False
                
                last_item = stack.pop()
                if bracket_dict[last_item] != char:
                    return False
        
        if stack:
            return False
        else:
            return True

Time Complexity: O(n)

 

설명

이 문제의 핵심은 stack data structure이다. stack은 기본적인 데이터 스트럭쳐중 하나로 가장 마지막에 들어온 object가 가장 처음 나가는 principle을 가지고 있다. 이를 LIFO (Last In First Out) 라고도 한다. 탑을 쌓는다고 생각하면 편하다. (물건을 하나씩 위로 쌓고 가장 위 물건을 가장 먼저 빼는 방식)

 

stack의 기본 원리를 생각하면서 이 문제를 접근하면 매우 쉽다. stack 하나를 생성하고 string을 iterate하면서 괄호가 valid한지 체크하면 된다.

 

for 루프 내에서 괄호 char를 하나씩 체크한다.

먼저 괄호가 opening bracket ("(, {, [") 일 경우, stack에 집어넣는다. 

만약 괄호가 closing bracket ("), }, ]") 일 경우, stack에서 가장 마지막 element를 빼내서 그 element가 괄호와 매치가 되는 bracket일 경우 루프를 계속 돌리지만, 만약 매치가 되는 bracket이 아닐 경우 그 string은 valid한 게 아니게 된다. 그러므로 바로 False를 리턴한다.

 

마지막으로 stack에 element가 있는지 확인한다. 없으면 true, 있으면 false. s = "{([" 와 같은 케이스를 테스트하기 위함이다. 이렇게 되면 for 루프는 끝까지 돌아가지만 stack에 모든 괄호가 남게 되기 때문이다. 이런 경우는 valid parentheses가 아니다.

 

짧은 답

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        bracket_dict = {"{": "}", "[": "]", "(": ")"}

        for char in s:
            if char in ("{", "[", "("):
                stack.append(char)
            elif not stack or bracket_dict[stack.pop()] != char:
                return False
        
        return not stack

 

노트

이 문제도 entry level coding test에 많이 나온다. stack 데이터 스트럭쳐를 이용하는 가장 유명한 문제이기도 하다. simple datastructure 를 잘 이용하는지도 테스트를 할 수 있고 기본적인 알고리즘의 이해를 평가하기 쉬운 문제이다. 

 

참고로 위 답 코드에도 썼지만 ("{", "[", "(")와 같은 () 는 list가 아니고 set다. 둘의 다른 점은 list는 element의 순서가 있고 list의 find operation이 O(n)이지만 set는 element의 순서가 없고 find operation은 O(1) 이다. set는 그냥 key dictionary라고 생각하면 편하다. 

 

출처