값 n이 주어졌을 때, 여는 괄호와 닫는 괄호가 각각 n개씩 포함된 모든 유효한(well-formed) 괄호 조합을 생성해야 합니다. 예를 들어 n = 3이라면 다음과 같은 결과 집합이 만들어집니다.
["()()()", "()(())", "(())()", "(()())", "((()))"]
문제 해결 접근 방식
이 문제는 백트래킹(backtracking) 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 문자열을 하나씩 확장해 가되, 어느 시점에서도 닫는 괄호의 개수가 여는 괄호보다 많아지지 않도록 제약을 거는 것입니다.
구체적인 알고리즘은 다음과 같습니다.
- 재귀 메서드 genParenthesisRec()를 정의합니다. 이 메서드는 left(사용 가능한 여는 괄호 수), right(사용 가능한 닫는 괄호 수), temp(현재까지 만든 문자열), result(결과를 저장할 배열)를 매개변수로 받습니다. 초기 상태에서 result 배열은 비어 있습니다.
- left = 0이고 right = 0이면, 즉 두 종류의 괄호를 모두 사용했다면 temp를 result에 추가하고 재귀 호출을 종료합니다.
- left > 0인 경우, 여는 괄호 '('를 붙인 뒤 left를 1 감소시키며 재귀 호출합니다.
- right > left인 경우에만 닫는 괄호 ')'를 붙일 수 있습니다. 이 조건 덕분에 이미 열린 괄호가 존재할 때만 닫는 괄호가 추가되어, 항상 균형 잡힌 유효한 문자열만 생성됩니다.
예제 코드 (Python)
다음 구현을 보면 동작 방식을 더 명확하게 이해할 수 있습니다.
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
result = []
self.generateParenthesisUtil(n, n, "", result)
return result
def generateParenthesisUtil(self, left, right, temp, result):
if left == 0 and right == 0:
result.append(temp)
return
if left > 0:
self.generateParenthesisUtil(left - 1, right, temp + '(', result)
if right > left:
self.generateParenthesisUtil(left, right - 1, temp + ')', result)
ob = Solution()
print(ob.generateParenthesis(4))입력
4
출력
["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"]
복잡도 분석
n쌍의 괄호로 만들 수 있는 유효한 조합의 개수는 카탈란 수(Catalan number) C(n)이며, 대략 4ⁿ / (n√n)에 비례해 증가합니다. 따라서 시간 복잡도와 공간 복잡도는 모두 O(4ⁿ / √n)입니다. 백트래킹 조건(right > left) 덕분에 유효하지 않은 경로는 조기에 차단되므로, 단순히 모든 경우를 탐색하는 브루트포스 방식보다 훨씬 효율적입니다.