Generate Parentheses

문제

LeetCode 22. Generate Parentheses. 정수 n 이 주어지면 괄호 n 쌍으로 만들 수 있는 올바른 괄호 문자열을 모두 반환한다. 제약은 1 ≤ n ≤ 8 이다.

올바른 괄호 문자열은 모든 ( 가 자기보다 뒤에 오는 ) 하나와 빠짐없이 짝지어지는 문자열이다. n = 3 이면 다음 다섯 개가 답이다.

((()))  (()())  (())()  ()(())  ()()()

반환값은 개수가 아니라 문자열 목록이다.

올바른 괄호 문자열 판별하기

아래 세 풀이는 모두 같은 판별 기준 위에 서 있다. 문자열을 왼쪽부터 읽으면서 ( 를 만나면 1 을 더하고 ) 를 만나면 1 을 뺀다. 이 값을 balance 라고 부르자. balance 는 “지금까지 열렸는데 아직 닫히지 않은 ( 의 개수” 다.

올바른 문자열이려면 두 조건을 모두 만족해야 한다.

1. 읽는 도중 balance 가 한 번도 음수가 되지 않는다. 음수가 됐다면 짝이 될 ( 없이 ) 가 나온 것이다.
2. 끝까지 읽었을 때 balance 가 0 이다. 0 보다 크면 닫히지 않은 ( 가 남은 것이다.

예를 들어 ())( 는 세 번째 글자에서 balance 가 -1 이 되어 1번 조건에서 탈락하고, (() 는 끝에서 balance 가 1 이라 2번 조건에서 탈락한다.

풀이 1: 전부 만들고 검사하기

가장 먼저 떠올리기 쉬운 방법이다. 길이 2n 인 문자열의 각 자리에 ( 또는 ) 를 넣어 가능한 문자열을 전부 만들고, 앞 절의 판별 기준을 통과한 것만 모은다.

from itertools import product
 
 
class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        def valid(s):
            balance = 0
            for ch in s:
                balance += 1 if ch == "(" else -1
                if balance < 0:
                    return False
            return balance == 0
 
        return ["".join(p) for p in product("()", repeat=2 * n) if valid(p)]

자리가 2n 개이고 자리마다 선택지가 둘이므로 후보는 $2^{2n}=4^n$ 개다. 후보 하나를 검사하는 데 길이 2n 만큼 걸린다. n = 8 이면 후보 65,536 개를 만들어서 그중 1,430 개(약 2.2%)만 남긴다.

제약이 n ≤ 8 로 작아서 이 방법도 시간 안에 통과한다. 다만 버리는 후보가 대부분이다. ) 로 시작하는 후보는 첫 글자에서 이미 1번 조건을 어겼는데도, 나머지 2n - 1 글자를 다 채운 뒤에야 검사를 받는다. 후보 전체의 절반이 이런 경우다.

풀이 2: 백트래킹으로 틀릴 후보를 처음부터 만들지 않기

풀이 1의 낭비를 줄이려면 검사를 맨 끝에서 하지 말고 글자를 붙이는 순간마다 하면 된다. 이 글자를 붙이면 올바른 문자열이 될 가능성이 사라지는지를 바로 판단하고, 사라진다면 그 글자는 붙이지 않는다.

이렇게 “선택을 하나 해서 다음 단계로 내려가고, 그 선택으로 할 일을 다 마치면 돌아와서 다른 선택을 해 보는” 탐색을 백트래킹(backtracking)이라고 한다. 선택지를 가지로 하는 트리를 DFS 로 훑는 것과 같다. 가망 없는 가지를 미리 잘라내는 것을 가지치기(pruning)라고 부른다.

글자를 붙여도 되는 조건

지금까지 만든 문자열에 대해 두 숫자만 알면 된다. 지금까지 쓴 ( 의 개수 opened 와 ) 의 개수 closed 다. balance 는 opened - closed 와 같다.

• ( 는 opened < n 일 때 붙일 수 있다. 쓸 수 있는 ( 는 모두 n 개다.
• ) 는 closed < opened 일 때 붙일 수 있다. 붙인 뒤에도 balance 가 음수가 되지 않으려면 지금 balance 가 1 이상이어야 한다. 판별 기준의 1번 조건을 만드는 도중에 지키는 것이다.

2번 조건은 따로 확인하지 않아도 저절로 지켜진다. 길이가 2n 이 됐다면 opened + closed = 2n 인데, 위 두 규칙 때문에 closed ≤ opened ≤ n 이다. 이 셋을 동시에 만족하는 경우는 opened = closed = n 뿐이므로 balance 가 0 이다. 그래서 길이 2n 에 도달한 문자열은 검사 없이 바로 답에 넣는다.

코드

class Solution:
    def generate(self, curr, opened, closed, n, result):
        if 2 * n == len(curr):
            result.append(curr)
            return
 
        if opened < n:
            self.generate(curr + "(", opened + 1, closed, n, result)
        if opened > closed:
            self.generate(curr + ")", opened, closed + 1, n, result)
 
    def generateParenthesis(self, n: int) -> list[str]:
        result = []
        self.generate("", 0, 0, n, result)
        return result

결과 리스트 result 는 맨 바깥에서 하나 만들어 모든 재귀 호출에 같은 객체로 넘긴다. 재귀 함수는 아무것도 반환하지 않고 이 리스트를 채우기만 한다.

n = 2 로 따라가 보기

""
└─ "("                 closed == opened 이므로 ) 는 붙일 수 없다
   ├─ "(("             opened == n 이므로 이제 ( 는 붙일 수 없다
   │  └─ "(()"
   │     └─ "(())"     길이 4, 답에 추가
   └─ "()"
      └─ "()("
         └─ "()()"     길이 4, 답에 추가

빈 문자열에서는 ) 를 붙일 수 없으니 ( 한 갈래만 있다. ( 에서는 두 조건이 모두 참이라 처음으로 갈래가 둘로 나뉜다. 왼쪽 갈래 (( 는 ( 를 다 썼으므로 ) 만 붙여 (()) 가 되고, 오른쪽 갈래 () 는 다시 ( 하나와 ) 하나를 붙여 ()() 가 된다.

트리의 모든 갈래가 끝까지 내려가서 답이 된다. 중간에 막혀서 버려지는 문자열이 없다. 풀이 1과 비교하면 n = 8 에서 풀이 1은 후보 65,536 개를 만드는 반면, 이 풀이의 재귀 호출은 6,917 번이다. 이 숫자는 n = 1–8 에 대해 직접 세어 확인했다.

갈림길은 독립된 if 두 개로 쓴다

두 조건을 if / else 로 쓰면 코드가 잘 돌아가는 것처럼 보이지만 답이 하나만 나온다. if / else 는 둘 중 하나만 고르는 구조라서 재귀가 한 줄로만 이어지고 트리가 갈라지지 않는다.

if opened < n:
    self.generate(curr + "(", ...)
else:
    self.generate(curr + ")", ...)

이렇게 쓰면 ( 를 다 쓸 때까지 ( 만 붙이므로 n = 3 에서 ((())) 하나만 나온다. 조건을 opened <= closed and opened < n 처럼 바꾸면 이번에는 열린 괄호가 다 닫혔을 때만 새로 열게 되어 ()()() 하나만 나온다. (() 처럼 ( 와 ) 를 둘 다 붙일 수 있는 순간에 두 갈래를 모두 가 봐야 나머지 답이 나온다.

if / else 에서 else 쪽은 ) 를 붙여도 되는지를 따로 확인하지 않는다는 점도 다르다. 위 코드에서는 opened == n 일 때만 else 로 가고 그때는 닫을 ( 가 항상 남아 있어서 우연히 맞았을 뿐이다. 독립된 if 두 개로 바꾸면 closed < opened 를 직접 써야 한다. 빠뜨리면 ) 로 시작하는 문자열까지 만들어진다.

다음 글자를 붙일 때 curr += "(" 처럼 변수 자체를 바꾸지 않고 curr + "(" 를 인자로 넘기는 것도 같은 이유다. 첫 번째 if 에서 curr 를 바꿔 버리면 그 ( 가 두 번째 if 의 curr 에도 남는다. 새 문자열을 만들어 넘기면 각 갈래가 자기 몫의 문자열을 따로 가지므로, 재귀에서 돌아온 뒤 붙인 글자를 지우는 되돌리기 코드가 필요 없다.

풀이 3: 첫 ( 의 짝을 기준으로 쪼개기

풀이 2가 글자를 왼쪽부터 하나씩 붙였다면, 이 풀이는 올바른 문자열의 구조를 이용해 작은 답들을 조립한다.

모든 답은 (A)B 꼴이다

비어 있지 않은 올바른 문자열은 반드시 ( 로 시작한다. 이 첫 ( 와 짝을 이루는 ) 의 위치를 찾으면 문자열이 세 부분으로 나뉜다.

 (   A   )   B
 ↑       ↑
 첫 (    그 짝인 )

• A 는 첫 ( 와 그 짝 사이에 있는 부분이다. 짝이 맞는 괄호 안쪽이므로 A 도 올바른 문자열이다(빈 문자열일 수 있다).
• B 는 짝 ) 뒤에 남은 부분이다. 앞부분이 완전히 닫혔으므로 B 도 올바른 문자열이다(빈 문자열일 수 있다).

괄호 쌍은 모두 n 개이고 바깥 ( ) 가 한 쌍을 쓰므로, A 가 c 쌍이면 B 는 n - 1 - c 쌍이다. c 는 0 부터 n - 1 까지 가능하다.

거꾸로 c 쌍짜리 올바른 문자열 A 와 n - 1 - c 쌍짜리 올바른 문자열 B 를 아무거나 골라 "(" + A + ")" + B 를 만들면 항상 n 쌍짜리 올바른 문자열이 된다. c 가 다르면 첫 ( 의 짝 위치가 다르므로 같은 문자열이 두 번 만들어지지 않는다. 따라서 이 조립으로 답이 빠짐없이, 중복 없이 나온다.

n = 3 으로 확인하면 다음과 같다.

c (A 의 쌍 수)	가능한 A	가능한 B	만들어지는 답
0	""	(()), ()()	()(()), ()()()
1	()	()	(())()
2	(()), ()()	""	((())), (()())

2 + 1 + 2 = 5 개로 답 다섯 개가 모두 나온다.

코드

from functools import lru_cache
 
 
class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        @lru_cache(maxsize=None)
        def gen(k):
            if k == 0:
                return [""]
            out = []
            for c in range(k):
                for inside in gen(c):
                    for after in gen(k - 1 - c):
                        out.append("(" + inside + ")" + after)
            return out
 
        return gen(n)

gen(k) 는 k 쌍짜리 올바른 문자열 목록을 돌려준다. gen(3) 을 구하는 동안 gen(1), gen(2) 가 여러 번 필요해지는데, @lru_cache 가 한 번 계산한 결과를 저장해 두었다가 같은 인자로 다시 불리면 계산 없이 돌려준다. 이렇게 이미 계산한 결과를 저장해 재사용하는 기법을 memoization 이라고 한다. 작은 k 의 답으로 큰 k 의 답을 만드는 구조라서 동적 계획법(dynamic programming)으로 볼 수도 있다.

세 풀이 비교

풀이	문자열을 만드는 방식	버리는 후보	시간
전부 만들고 검사	모든 자리 조합을 만든 뒤 판별	대부분 ($n=8$ 에서 약 98%)	$O(4^n\cdot n)$
백트래킹	한 글자씩 붙이며 조건이 맞는 갈래만 탐색	없음	$O(C_n\cdot n)$
(A)B 로 쪼개기	작은 답 두 개를 조립	없음	$O(C_n\cdot n)$

$C_n$ 은 답의 개수다(다음 절). 백트래킹과 쪼개기 풀이는 답 하나를 만드는 데 길이 2n 만큼의 작업을 하므로 둘 다 “답의 개수 × 길이” 에 비례한다. 답을 모두 출력해야 하는 문제라서 어떤 풀이도 이보다 빠를 수는 없다. time complexity 표기는 해당 노트 참고.

면접이나 코딩 테스트에서 가장 많이 쓰는 것은 백트래킹이다. 판별 기준에서 바로 이어지는 발상이라 설명하기 쉽고, 같은 틀이 순열·조합·부분집합 생성 문제에도 그대로 쓰인다. 쪼개기 풀이는 답의 개수를 세는 식으로 바로 이어진다는 점에서 의미가 있다.

답의 개수는 카탈란 수다

n 이 1 부터 8 까지일 때 답의 개수는 1, 2, 5, 14, 42, 132, 429, 1430 이다. 이 수열을 카탈란 수(Catalan number)라고 한다.

앞의 쪼개기 풀이가 그대로 개수 점화식이 된다. A 를 고르는 경우의 수와 B 를 고르는 경우의 수를 곱하고, 가능한 c 에 대해 더하면 된다.

$$C_0=1,C_k=\sum _{c=0}^{k-1}{C}_c{C}_{k-1-c}$$

이 점화식을 풀면 닫힌 식이 나온다.

$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\approx \frac{4^n}{n^{3/2}\sqrt{\pi }}$$

기호	뜻
$C_k$	괄호 k 쌍으로 만들 수 있는 올바른 문자열의 개수
$c$	첫 ( 와 그 짝 사이에 들어가는 괄호 쌍의 수
$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$	2n 자리 중 ( 가 들어갈 n 자리를 고르는 경우의 수

근사식을 보면 풀이 1이 왜 통과하는지도 알 수 있다. 풀이 1의 후보 수 $4^n$ 과 답의 수 $C_n$ 의 비는 대략 $n^{3/2}\sqrt{\pi }$ 다. 즉 답 자체가 이미 $4^n$ 에 가깝게 늘어나고, 풀이 1의 낭비는 그 위에 곱해지는 다항식 크기의 배수다. n = 8 에서 실제 비는 65,536 / 1,430, 약 46 배다.

카탈란 수는 괄호 짝짓기와 구조가 같은 다른 문제에서도 나온다. 노드 n 개로 만들 수 있는 Binary Tree 모양의 수도 $C_n$ 인데, 루트의 왼쪽 서브트리에 노드 c 개, 오른쪽에 n - 1 - c 개를 두는 분해가 (A)B 분해와 똑같기 때문이다.

References

• LeetCode 22. Generate Parentheses
• Catalan number - Wikipedia