[LeetCode]Generate Parentheses

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

Generate Parentheses - LeetCode

 

문제 분석

주어진 n개의 괄호를 가지고 가능한 괄호의 조합을 모두 구하는 문제입니다.

 

처음 시도한 답안

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

        def dfs(char, remaining_open_braket, remaining_close_braket, answer):
            # 모든 괄호가 사용되면 정답에 추가함.
            if len(char) == 2 * n:
                answer.append(char)
                return 

            # 열려있는 괄호가 사용 가능할 때만 추가, 열린 괄호부터 사용
            if remaining_open_braket > 0:
                dfs(char + '(', remaining_open_braket-1, remaining_close_braket, answer)
            
            # 남은 닫혀있는 괄호의 갯수가 더 많을때만 괄호를 닫을 수 있음.
            if remaining_open_braket < remaining_close_braket:
                dfs(char + ')', remaining_open_braket, remaining_close_braket-1, answer)

        dfs('', n, n, answer)

        return answer

접근 방법

1. dfs를 통해 재귀 방식으로 괄호쌍을 만들어 나간다.
2. 만약 만들어진 글자가 n*2 라면 (모든 괄호가 사용되면) 정답에 추가한다.
3. 열린 괄호가 사용가능한 경우에는 ( 를 추가한다.
   1. 재귀 호출을 통해 남아있는 열린 괄호의 수를 한개 감소하고, ( 문자를 추가한다.
4. 남아있는 닫힌 괄호의 수가 남아있는 열린 괄호의 수보다 많을때만 ) 를 추가한다.
   닫힌 괄호가 더 많이 사용된다면 valid한 parentheses가 되지 않기 때문이다.
   1. 재귀 호출을 통해 남아있는 닫힌 괄호의 수를 한개 감소하고, ) 문자를 추가한다.

dfs 탐색을 통해서 parentheses를 만드는 방법입니다. 다음의 조건들을 만족해야 올바른 괄호를 만들 수 있습니다.

• 가장 처음에는 열린 괄호부터 사용해야 합니다.
• 닫힌 괄호의 수는 항상 열린 괄호의 수보다 적거나 같아야 합니다.
• 재귀적으로 호출하면서 모든 괄호가 사용되면 정답에 추가합니다. (혹은, 남아있는 열린, 닫힌 괄호의 수가 모두 0일 때)

( ) 두개의 괄호를 가지고 이진 트리의 형태로 괄호쌍을 그려나가다 보면 dfs 탐색으로 해결할 수 있다는 힌트를 얻을 수 있습니다.