•
문제 설명 : n개의 괄호 쌍으로 만들 수 있는 유효한 괄호 조합을 반환
•
풀이 방법
◦
방법은 백트래킹과 DP 2가지이다.
◦
개인적으로는 백트래킹이 익숙하여 백트래킹으로 진행하였다.
◦
열린 괄호 갯수와 닫힌 괄호 갯수를 확인하며, 최대한 적은 재귀 탐색으로 처리하며 진행했다.
•
시간복잡도 :
•
성공 코드 (백트래킹)
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
def dfs(current_str, open_count, close_count):
if len(current_str) == n * 2:
result.append(current_str)
return
if open_count < n:
dfs(current_str + "(", open_count + 1, close_count)
if 0 < open_count and close_count < open_count:
dfs(current_str + ")", open_count, close_count + 1)
dfs("", 0, 0)
return result
Python
복사
•
성공코드 (DP)
DP는 점화식을 어떻게 찾느냐가 관건인 것 같다.
개인적으로는 n-1 결과만 사용하는 점화식을 사용했었는데, 예외 처리에 실패하며 DP로는 해결하지 못하였다.
솔루션이나 검색으로 확인해보니, 아래와 같은 점화식을 세워서 사용하였다.
→ 확인해보니, 카탈랑 수 라고하는 점화식이었다. 조합과 관련된 알고리즘에서 자주 보일듯 하다.
이때 왼쪽에만 추가 괄호를 설정하는 이유는 괄호의 규칙(열기로 시작/닫기로 끝내기)를 위해서이다.
그래서 사실 오른쪽 Item(right)부분에 괄호를 설정해도 푸는데는 문제가 없다.
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
dp = [[] for _ in range(n + 1)]
dp[0] = [""]
for i in range(1, n + 1):
current_list = []
for j in range(i):
for left in dp[j]:
for right in dp[i - j - 1]:
# n = 3일때
# {n=0결과} + {n=2결과} 조합
# {n=1결과} + {n=1결과} 조합
# {n=2결과} + {n=0결과} 조합
# 위 처럼 사용한다.
current_list.append(f"({left}){right}")
dp[i] = current_list
return dp[n]
Python
복사