[leetcode][Medium][Stack] 22. Generate Parentheses 힌트, 풀이, 해설 (python)

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

Generate Parentheses - LeetCode

 

힌트 

https://www.youtube.com/watch?v=s9fokUqJ76A

어떻게 풀어야 하나 30분 정도 고민하다가, 위 영상을 참고해서 힌트를 얻어왔다. 

규칙은 close 갯수 < open 갯수 여야 한다는 것 ! 

 

 

1차 풀이 

그 규칙을 참고해서 bfs로 재귀 함수를 사용해서 문제를 풀었다. 

하면서 stack 유형으로 neetcode에서 제시한 문제지만 dfs..로 접근하는게 맞나 했지만, 

그래도 푸는 것에 의의를 두고 풀었다. 

class Solution(object):
    res = [] 
    
    def dfs(self, current, n):
        openCnt = current.count("(")
        closeCnt = current.count(")")
        
        if len(current) == 2 * n:
            if openCnt == n and closeCnt == n:
                self.res.append(current)
            return;
        else:            
            # close 갯수 < open 갯수 
            if closeCnt <= openCnt:
                self.dfs(current + "(", n)
                self.dfs(current + ")", n)
    
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self.res = [] # 테스트 케이스 전에 예전에 돌린 값 초기화 
        self.dfs("(", n)
        return self.res

 

 

해설

위 영상에서 제시한 풀이. 

stack에다가 넣고 backtrack으로 함수를 돌면서 푼다. 

 

 def generateParenthesis(self, n):
        # only add open paranthesis if open < n
        # only add a closing paranthesis if closed < open 
        # valid IIF open == closed == n 
        
        stack = [] 
        res = [] 
        
        def backtrack(openN, closedN):
            if openN == closedN == n:
                res.append("".join(stack))
                return 
            
            if openN < n:
                stack.append("(")
                backtrack(openN + 1, closedN)
                stack.pop() # clean up .. 
                
            if closedN < openN:
                stack.append(")")
                backtrack(openN, closedN + 1)
                stack.pop()
                
        backtrack(0,0)
        return res