[LeetCode] 22 | Generate Parentheses

 

 

 

22 | Generate Parentheses
https://leetcode.com/problems/generate-parentheses/

 

 

 

 

 

 

작성 코드

 

 

class Solution:

                
    def generateParenthesis(self, n: int) -> List[str]:
        
        combs = []
        def dfs(s, n, leave, depth):
            leave_tmp = leave[:]
            if depth == 2 * n:
                combs.append(s)
                print(s)
                return 
            if leave_tmp[0] == 0:
                print(1, s)
                s += ")"
                leave_tmp[1] -= 1
                dfs(s, n, leave_tmp, depth + 1)

            else:
                if leave_tmp[0] == leave_tmp[1]:
                    print(2, s)
                    s += "("
                    leave_tmp[0] -= 1
                    dfs(s, n, leave_tmp, depth + 1)
                elif leave_tmp[0] < leave_tmp[1]:
                    print(3, s)
                    s += ")"
                    leave_tmp[1] -= 1
                    dfs(s, n, leave_tmp, depth + 1)
                    
                    print(4, s, leave_tmp)
                    s = s[:-1] + "("
                    leave_tmp[1] += 1
                    leave_tmp[0] -= 1
                    dfs(s, n, leave_tmp, depth + 1)
        
        
        dfs("", n, [n, n], 0)
        return combs

 

 

• leave_tmp 에는 남은 열린 괄호와 닫힌 괄호의 수가 들어감
• depth 가 2 * n 으로 문자열이 완성되었다면 return
• 열린 괄호의 개수가 0개라면 닫힌 괄호를 작성하는 방법 밖에 없음
• 열린 괄호의 개수와 닫힌 괄호의 개수가 같다면 열린 괄호를 작성하는 방법 밖에 없음
• 열린 괄호보다 닫힌 괄호가 크다면 열린 괄호 혹은 닫힌 괄호를 작성할 수 있음 -> 이 경우 때문에 dfs 호출하는 것을 매번 적을 수 밖에 없었음

 

• 통과는 했으나 조잡한 풀이, dfs 를 여러번 써야하는 것이 깔끔하지 못 함
• comb 를 return 해주고 싶은데 언제 함수가 끝나며, 어떻게 return 해줘야하는지 모르겠어서 함수 내 함수로 작성함

 

 

 

이상 코드

 

 

class Solution:
    def generateParenthesis(self, n):
        def generate(p, left, right, parens=[]):
            if left:
                generate(p + '(', left-1, right)
            if right > left: 
                generate(p + ')', left, right-1)
            if not right:    
                parens += p,
            return parens
        return generate('', n, n)

 

• 생성되는 순서는 ["((()))","(()())","(())()","()(())","()()()"]
• left, right 는 남아있는 열린 괄호, 닫힌 괄호의 개수
• if - elif - else 로 이어지는 것이 아니기 때문에 함수가 호출되고 return 되면 밑의 조건문으로 내려가면서 완성시킴

 

 

 

학습

 

• 반복되는 코드는 되도록이면 작성하지 않도록
• 재귀함수의 호출, 종료 원리에 대해 이해할 수 있는 좋은 코드