[Leetcode] 20. Valid Parentheses_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '20. Valid Parentheses'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Valid Parentheses' 알고리즘 문제

 

STEP 2. 'Valid Parentheses' 코드(code)

 

STEP 3. 'Valid Parentheses' solution

 

반응형

 

STEP 1. '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.
   (열린 대괄호는 올바른 순서로 닫아야 합니다.)

Constraints:

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

---

STEP 2. 'Valid Parentheses' 코드(code)

 

Dictionary를 통해, key와 value 관계로 계산하려고 했습니다. 2n과 2n+1은 서로 pair거나, ( [ ] )와 같이 양극단에서 합쳐지는 경우를 고려해서 코드를 작성했습니다. 다만, "(}{)" 등 경우와 같이, 다양한 경우를 전부 해결하지 못 해서, 결론적으로 runtimeerror, time limit exceeded가 발생했습니다.

 

아래 코드는 위의 접근 방식에 맞춰 작성한 코드입니다.

class Solution:
    def isValid(self, s: str) -> bool:
        # check even number
        brakets = {'(':')', '{':'}', '[':']'}
        i = 0
        l = 0
        r = len(s) - 1
        
        def mirror_string(l, r):
            while l < r :
                if brakets[s[l]] == s[r]:
                    l += 1
                    r -= 1
                else:
                    return False
                
            return True       
    
        # check odd number
        if len(s) % 2 == 1:
            return False
        
        # if first letter is closed
        if s[i] in brakets.values():
            return False
        
        while i < len(s):
            # compare the even number of s and brakets
            if s[i] in brakets.values():
                return False
            
            if s[i+1] == brakets[s[i]]:
                i += 2
            else:
                return mirror_string(l, r)

        return True

---

STEP 3. 'Valid Parentheses' solution

 

추가적으로, Leetcode에서 공유된 코드를 살펴보겠습니다.

 

■ Runtime: 39 ms, faster than 74.21% of Python3 online submissions for Valid Parentheses.
■ Memory Usage: 13.8 MB, less than 69.67% of Python3 online submissions for Valid Parentheses.

 

class Solution:
    def isValid(self, s: str) -> bool:
        d = {'(':')', '{':'}','[':']'}
        stack = []
        for i in s:
            if i in d:  # 1
                stack.append(i)
            elif len(stack) == 0 or d[stack.pop()] != i:  # 2
                return False
        return len(stack) == 0 # 3

 

 

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '20. Valid Parentheses'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.