LeetCode 22(Generate Parentheses, Python)

1. 문제 링크

• https://leetcode.com/problems/generate-parentheses

Generate Parentheses - LeetCode

2. 문제 설명

• 주어진 n쌍의 괄호로, 올바르게 구성된 괄호의 모든 조합을 생성하여 해당 list를 반환
• 예시) n=3이면 3쌍의 괄호 모든 조합 반환
  • ["((()))", "(()())", "(())()","()(())","()()()"] 
  • 여기서 'well-formd'한 괄호라는 조건이 주어져있는데
    • 이는, 여는 괄호 '('와 닫는 괄호 ')가 올바른 순서와 짝을 이루는 것을 의미.
    • 예를 들어 )(는 올바른 짝을 이루지 못했으므로 well-formed하지 않음

3. 처음 풀이

• 가장 나이브하게는, 전체 경우의 수를 list로 쌓고, well formed 구조인지 판단하여 아니라면 list에서 제외하는 것을 생각했는데,
  
  • 그러면 runtime이 너무 안나올 것 같아서, 
• "재귀"를 활용
  • 우선 n=1일 때는 ["()"]로 고정을 해두고, 
  • n이 1보다 큰 경우에 대해서는, 이전 함수의 결과값에 for문을 돌리면서 
    • '('와 ')'를 결과값 중간에 삽입하는 구조로 작성.
    • 여기서 중복이 발생할 수 있으므로, 처음에 output을 set()으로 설정한 뒤, add하다가,
    • list로 변형해서 반환하는 식으로 함수를 짬

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        if n==1:
            return ["()"]
        
        output = set()
        if n>1:
            for i in self.generateParenthesis(n-1):
                for j in range(len(i)):
                    output.add('(' + i[:j] + ')' + i[j:])
        return list(output)

• runtime이 돌릴 때마다 약간 씩 차이가 나긴 했지만, 최대 82% beats로 나쁘지 않았음.
• 다만, 내 로직에서는 중복된 애들도 계속 add하는 구조가 되버리니, 더 좋은 풀이가 있을거라 생각

4. 다른 풀이

• runtime 98% beats한, 잘 푼사람들이 대부분 사용했던 풀이
  • 우선 left, right = 0,0, 문자열 ''에서 시작을 하고,
    • 왼쪽이 n보다 적은 경우 문자열 s에 '('을 추가, 
    • 오른쪽이 왼쪽보다 적은 경우 ')'를 추가
      
      • left, right, s = 1, 0 , '('가 된 경우
      • 오른쪽이 왼쪽보다 적으므로
        • left, right, s = 1,1,'()'로 업데이트가 됨 
  • 이걸 left < n일 때까지 재귀 수행

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(left, right, s):
            # 괄호 쌍이 2n개가 됐을 때 결과에 추가하고 종료합니다.
            if len(s) == n * 2:
                res.append(s)
                return 

            # 왼쪽 괄호가 n보다 적은 경우 '('를 추가합니다.
            if left < n:
                dfs(left + 1, right, s + '(')

            # 오른쪽 괄호가 왼쪽보다 적은 경우 ')'를 추가합니다.
            if right < left:
                dfs(left, right + 1, s + ')')

        # 재귀함수 시작
        res = []
        dfs(0, 0, '')
        return res

 

• 재귀함수 동작 방식은 아래와 같음(DFS)

  (0, 0, '')
      |
(1, 0, '(')  
   /           \
(2, 0, '((')      (1, 1, '()')
   /                 \
(2, 1, '(()')           (2, 1, '()(')
   /                       \
(2, 2, '(())')                (2, 2, '()()')
      |                              |
res.append('(())')             res.append('()()')

 

5. 배운 점

• 내가 짠 재귀는 이전 결과값을 불러오는 구조로만 되어있는데
• 정석으로 푼 풀이에서는 함수에 들어가는 인자 s를 재귀적으로 사용하면서, 중복 없이 필요한 조합 생성
• 아직 잘 푼 코드가 직관적으로 이해되지 않는데, 재귀 좀 더 공부할 필요가 있다