[LeetCode 풀이/python] 22. Generate Parentheses (medium)

 

문제 설명: n 쌍의 괄호가 주어졌을 때, 유효한 괄호 쌍들로만 이루어진 모든 조합을 생성하는 함수를 만드시오.

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

 

예시 1)

입력: n = 3  -->  출력: ["((()))","(()())","(())()","()(())","()()()"]

예시 2)

입력: n = 1  -->  출력: ["()"]

 

제한 조건:

• 1 <= n <= 8

------ * ------ * ------ * ------

 

[풀이 1안 (not a solution)]

• 접근법
  • DP / Recursion 이용
  • 가설 1: n pairs 의 괄호 쌍이 만들어지는 방식은 (n-1) pairs 괄호 쌍 각각에 대해 아래와 같은 두 가지 전략을 적용하는 것으로 나눌 수 있다 
    1. side (left or right) 에 새로운 괄호 하나를 추가하기
    2. 이를 새로운 괄호로 감싸기

 

• 코드 구현

def str_outerhug(sample):
    return "(" + sample + ")"

def str_leftside(sample):
    return "()" + sample

def str_rightside(sample):
    return sample + "()"
    
def generateParenthesis(self, n: int) -> List[str]:
    if n == 1:
        return ["()"]
    else:
        res = set()
        cand = generateParenthesis(n-1)
        for c in cand:
            res.add(str_outerhug(c))
            res.add(str_leftside(c))
            res.add(str_rightside(c))        
        return res
        

 

• 결과
  • n <= 3 일 때는 문제 없음
  • 하지만, n > 4 인 경우 해당 가설이 커버하지 못하는 경우가 존재함! (예: '(())(())' )  -->  가설 1 기각
  • 해당 케이스를 커버하는 새로운 전략을 놓친걸까? 아니면 아예 새로운 접근법이 필요한걸까? 
  • ==>  Discussion 페이지에서 상위에 있는 python 코드의 접근법을 참고해보자 :) 

 

[풀이 2안 (w/solution peeping)]

• 접근법
  • 역시나 DP / Recursion 이용
  • 하지만 n pairs 를 recursively 생성하는 방식을 보다 구조적으로(!) 구분하고 있음
    1. zero pair inside, afterwards (n-1) pairs  (예: '()(((...)))' , '()()((...))' )
       (참고: () = zero pair inside 인 괄호에 해당)
    2. 1 pair inside, afterwards (n-2) pairs  (예: '(())((...))' , '(())()(...)' )
    3. ( 중략 )
    4. (n-1) pairs inside  (예: '(((...)))' ) 

 

• 코드 구현

def generateParenthesis(self, n: int) -> List[str]:
    res = []
    if n == 0:
        return ['']
    else:
        t = 0
        while t < n:
            prefix = generateParenthesis(t)
            suffix = generateParenthesis(n-t-1)
            for pre in prefix:
                for suf in suffix:
                    tmp = '(' + pre + ')' + suf
                    res.append(tmp)
            t += 1

    return res
    

 

• 결과
  • 쨌든 통과는 했다...
  • 하지만 for 문을 두 번 돌린 탓에 시간복잡도 면에서 아주 후진 코드가 되었다 :] (faster than 19.56% 라니...)
  • 시간복잡도 면에서 보다 효율적인 코드로 수정이 필요해 보인다 헤헷

 

[풀이 3안]

• 접근법
  • 풀이 2안과 기본적으로 동일
  • 2안에서 prefix / suffix 부분을 구하는 과정에서 중복되는 연산이 누적 발생된다는 것을 깨달음 (이전에도 자주 하던 실수..)
  • 참고했던 접근법을 다시 코드까지 뜯어보니, 이중 리스트 형태로 memoization 테이블을 만들어 쓰고 있다!
  • ==> 그대로 베끼면 재미없으니, 딕셔너리 구조로 memoization 을 해보자

 

• 코드 구현

from collections import defaultdict

def generateParenthesis(self, n: int) -> List[str]:
    mem = defaultdict(list)
    mem[0].append('')
    
    for i in range(1, n + 1):
        for j in range(i):
            mem[i] += [ '(' + pre + ')' + suf for pre in mem[j] for suf in mem[i-j-1] ]

    return mem[n]
    

 

• 결과
  • 공간 복잡도는 살짝 늘었지만, 대신 시간 복잡도가 크게 줄었다 희희
  • memoization 테이블에 값을 추가하는 과정에서 bracket [] 안 두 개의 for loop 을 풀어서 써보니 시간이 좀 더 걸렸다
  • Discussion 을 보니 stack 을 이용하는 풀이도 있는 것 같던데 한 번 봐야겠다