[Leetcode] 22. Generate Parentheses_해설, 풀이, 설명

---

안녕하세요, HELLO

 

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

 

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

---

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

 

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

 

STEP 3. 'Generate Parentheses' 해설

 

STEP 4. 'Generate Parentheses' solution

 

반응형

 

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

 

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

n쌍의 괄호가 주어지며, 이를 활용해서 최대로 조합된 괄호쌍을 만들면 됩니다.

 

Constraints:

• 1 <= n <= 8

---

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

 

■ Runtime: 90 ms, faster than 7.16% of Python3 online submissions for Generate Parentheses.
■ Memory Usage: 14.1 MB, less than 76.82% of Python3 online submissions for Generate Parentheses.

 

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # only add open parenthesis if open < n
        # only add a closed parenthesis if closed < open
        # vaild IIF open == closed == n
        
        stack = []
        res = []

        def backtrack(openN, closedN):
            if openN == closedN == n:
                res.append("".join(stack))
                # Get back to previous backtrack function
                return
            
            if openN < n:
                stack.append("(")
                backtrack(openN + 1, closedN)
                stack.pop()
                
            if closedN < openN:
                stack.append(")")
                backtrack(openN, closedN + 1)
                stack.pop()

        backtrack(0, 0)
        return res

---

STEP 3. 'Generate Parentheses' 해설

 

neetcode_22. generate parentheses

알고리즘 방식은 3가지 변수 (n, open parentheses, closed parentheses)를 활용해서 가지치기 방식으로 업데이트하는 방식입니다.

 

1. 기본적으로 "("가 제일 먼저 입력됩니다.

2. open parentheses "("는 괄호 쌍 개수 n 보다 작습니다. (openN < n)

3. closed parentheses ")"는 open parentheses "("보다 작습니다. (closedN < openN)

4. 최종적으로 3가지 변수가 모두 같아지면, 알고리즘은 종료됩니다. (openN = closedN = n)

 

 

STEP 4. 'Generate Parentheses' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 178 ms, faster than 5.07% of Python3 online submissions for Generate Parentheses.
■ Memory Usage: 14.2 MB, less than 39.97% of Python3 online submissions for Generate Parentheses.

 

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(A = []):
            if len(A) == 2*n:
                if valid(A):
                    ans.append("".join(A))
                
            else:
                A.append("(")
                generate(A)
                A.pop()

                A.append(")")
                generate(A)
                A.pop()
                    
        def valid(A):
            bal = 0
            for c in A:
                if c == '(': bal += 1
                else: bal -= 1
                
                if bal <0 : return False
            return bal == 0
        
        ans = []
        generate()
        return ans

---

■ 마무리

 

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

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

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

감사합니다.