22. Generate Parentheses - 파이썬

이 문제는 dfs로 풀려다 뭔가 꼬여서 틀렸던 문제이다. 릿코드는 일단 200번까지 푸는게 목표인데 145번을 풀고 있는 지금 다시 풀어보니 풀렸다. Medium에서 알 수 있듯 그다지 어려운 문제는 아닌데 전형적인 문제라 남겨준다. 

 

문제

1. n이 주어졌을 때 가능한 괄호 닫기 모든 경우의 수. 

2. Parentheses가 무슨 뜻인지 몰라 검색했던 기억이 난다... ^^ 

 

풀이

1. 핵심은 "(" , 즉 괄호가 열려있던 적이 있어야 괄호 닫기 ")"를 사용할 수 있다는 점. n이 충분할 때 "((" 는 가능하지만 "())"는 불가능

2. n의 개수만큼 (를 사용 할 수 있고 사용할 때마다 스택에 )를 쌓아 둔다. 

3. 재귀와 스택을 활용

 

개선점

1. 무언가 코드가 너저분

2. 변수가 너무 많아 직관성이 떨어진다. 

 

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.dfs('', 0, n, res, [])
        return res
    def dfs(self, s, cnt, n, res, stack) :
        if len(s) == 2*n :
            res.append(s)
        if cnt != n :
            self.dfs(s+'(', cnt + 1, n, res, stack + [')'])
        if stack :
            s = s + stack.pop()
            self.dfs(s, cnt, n, res, stack)