[리트코드 (LeetCode)] Valid Parentheses (Python)

Valid Parentheses

• https://leetcode.com/explore/featured/card/top-interview-questions-easy/99/others/721/
• 분류: Top Interview Questions - Easy - Others

Explore - LeetCode

문제

• 주어진 문자열 s는 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’로만 구성되어 있다. 입력 받은 문자열이 유효한지 판별하라.
• type s: str / rtype: bool
• 입력 문자열이 유효한 기준
  1. 여는 괄호는 반드시 같은 종류의 닫는 괄호로 닫혀야 한다.
  2. 여는 괄호는 반드시 올바른 순서로 닫혀야 한다.
  3. 모든 닫는 괄호는 상응하는 같은 종류의 여는 괄호가 있어야 한다.

예시

Example 1:
Input: s = "()"
Output: true

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

Example 3:
Input: s = "(]"
Output: false

조건

• 입력 문자열 s의 길이 1~1만
• s는 '()[]{}' 으로만 구성됨

힌트

• char stack을 활용하라.
• 여는 괄호를 만났을 때 스택의 top에 push해라.
• 닫는 괄호를 만났을 때 스택 top이 상응하는 괄호인지 확인하고 맞다면 pop 하고, 아니라면 false를 반환하라.

풀이

스택과 딕셔너리를 활용한 풀이

 

힌트에서도 확인할 수 있듯이 전형적인 스택을 이용해 괄호 쌍 맞추는 문제다. 파이썬에서 스택은 list 자료형과 append, pop 함수를 활용한다. 스택 top은 stack[-1]로 확인할 수 있다. 각 연산의 시간복잡도는 O(1)이다. (append와 pop에 인자를 따로 주지 않은 경우)

 

우선 입력 받은 문자열의 길이가 홀수라면 반드시 짝이 맞지 않으므로 바로 false를 리턴하였다. 또한 모든 연산이 끝난 후에도 스택이 비어있지 않다면 (여는 괄호가 남아있다면) false를 반환했고, 아니라면 true를 반환했다.

스택이 비어있는 경우 스택 top에 접근하면 에러가 나므로 top에 접근하기 전 스택이 비어있지 않은지 확인했다. 그리고 딕셔너리 자료형을 이용해 괄호 검사와 짝 맞추기 코드를 간결하게 했다.

 

완성된 코드는 다음과 같다.

class Solution(object):
    def isValid(self, s):
        if len(s) % 2 != 0:
            return False
        dic = {'(':')', '{':'}', '[':']'}
        stack = []
        for ch in s:
            if ch in dic: # key로 여는 괄호인지 검사
                stack.append(ch)
            elif stack and dic[stack[-1]] == ch:
                stack.pop()
            else: # 닫는 괄호고 스택이 비어있거나 스택 top이 상응하는 짝이 아닌 경우
                return False
        if stack: # 모든 연산이 끝난 후에도 스택에 여는 괄호가 남아있다면
            return False
        else:
            return True

Runtime: 15 ms (beats 85.09%) / Memory Usage: 13.7 MB (beats 35.69%)

 

맨 마지막 코드를 return not stack 한 줄로 처리할 수도 있다. (스택이 비어있다면 true, 비어있지 않다면 false)

class Solution(object):
    def isValid(self, s):
        if len(s) % 2 != 0:
            return False
        dic = {'(':')', '{':'}', '[':']'}
        stack = []
        for ch in s:
            if ch in dic:
                stack.append(ch)
            elif stack and dic[stack[-1]] == ch:
                stack.pop()
            else: 
                return False
        return not stack

Runtime: 17 ms (beats 69.5%) / Memory Usage: 13.4 MB (beats 85.94%)

 

discussion 란을 보니 닫는 괄호를 key, 여는 괄호를 value로 넣은 경우도 있던데 큰 차이는 없지만 개인적인 의견으로는 지금 작성한 코드가 더 깔끔한 것 같다.