[알고리즘] Generate Parentheses

Leetcode의 Generate Parentheses 문제를 풀어보도록 하겠습니다.

문제

n 쌍의 괄호가 주어졌을 때, 괄호로 이루어진 유효한 문자열의 조합을 만들어내는 함수를 작성하라.
예를 들어, n = 3 이면, 함수의 리턴 값은 다음과 같다.

1
2
3
4
5
6
7
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

풀이

이 문제에서 괄호로 이뤄진 문자열은 어떤 조건을 만족해야 유효해질까요?

  1. (의 개수는 )의 개수와 동일해야 합니다.
  2. ()의 개수는 n개를 초과할 수 없습니다.

자 그럼, 빈 문자열부터 시작해서 위 조건을 만족하도록 괄호를 하나씩 더해나가보겠습니다.
n = 2 일 때, 다음과 같은 사고 과정을 거쳐서 2개의 유효한 문자열을 찾아낼 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
'('
'(('
'(((' => 조건 위반 : '(' 개수 > 2
'(()'
'(()(' => 조건 위반 : '(' 개수 > 2
'(())' => 유효한 문자열 #1
'()'
'()('
'()((' => 조건 위반 : '(' 개수 > 2
'()()' => 유효한 문자열 #2
'())' => 조건 위반 : '(' 개수 < ')' 개수
')' => 조건 위반 : '(' 개수 < ')' 개수

괄호의 종류가 () 이렇게 두 개이기 때문에 괄호를 더할 때 항상 두 가지 옵션이 생기는 것을 알 수 있습니다.
또한 (는 n을 초과하지 않는 선에서 계속해서 더해나갈 수 있자만, )는 n을 초과하면 안 될 뿐만 아니라, 먼저 나온 (의 개수도 초과하면 안됩니다.

위의 그림을 관찰해보면 여러 개의 경로를 가지는 트리 구조라는 것을 알 수 있습니다.
그리고 어떤 경로에서 괄호를 추가하다가 위의 조건을 만족하지 못하는 순간에 이르르면, 해당 경로는 더 이상 고려할 가치가 없어지는 것을 알 수 있습니다.

이렇게 트리 구조의 사고 과정은 일반적으로 재귀 알고리즘으로 구현이 가능합니다.

성능 측면에서 생각해봤을 때, 괄호로 이뤄진 문자열이 조건에 위반되었는지를 빠르게 판별하는 게 핵심이 되는 문제입니다.
매번 문자열 내의 모든 괄호를 세어서 유효한 문자열인지 계산해야 한다면 문자열이 길어질 수록 점점 느려질 것입니다.
하지만, ( 개수와 ) 개수를 저장해두고 괄호를 더할 때 마다 늘려간다면 단순히 대소 비교만으로도 해당 문자열이 유효한지 체크할 수 있습니다.

Python

파이썬은 함수 내에서 또 다른 함수를 선언할 수 있고, 안에 있는 함수에서 밖에 있는 함수의 변수에 접근이 가능합니다.
따라서 helper() 재귀 함수로 넘어가는 파라미터의 수를 최소화할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def generateParenthesis(self, n):
results = []

def helper(text, left, right):
if left == n and right == n:
return results.append(text)
if left > n or left < right:
return
helper(text + '(', left + 1, right)
helper(text + ')', left, right + 1)

helper('', 0, 0)
return results

Java

반면 자바에서는 불가피하게 재귀 함수의 파라미터 수가 늘어나게 되었습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public List<String> generateParenthesis(int n) {
List<String> results = new ArrayList<>();
helper("", 0, 0, n, results);
return results;
}

private void helper(String text, int left, int right, int n, List<String> results) {
if (left == n && right == n) {
results.add(text);
return;
}
if (left > n || left < right) return;
helper(text + "(", left + 1, right, n, results);
helper(text + ")", left, right + 1, n, results);
}
}

호출 트리

위 코드가 어떻게 재귀적으로 호출되는지 이해를 돕기위해, n = 3 일 때 기준으로 호출 트리를 간단하게 시각화 해보았습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
F('', 0, 0)
F('(', 1, 0)
F('((', 2, 0)
F('(((', 3, 0)
F('((((', 4, 0) => X : left > n
F('((()', 3, 1)
F('((()(', 4, 1) => X : left > n
F('((())', 3, 2)
F('((())(', 4, 2) => X : left > n
F('((()))', 3, 3) => O : add '((()))'
F('(()', 2, 1)
F('(()(', 3, 1)
F('(()((', 4, 1) => X : left > n
F('(()()', 3, 2)
F('(()()(', 4, 2) => X : left > n
F('(()())', 3, 3) => O : add '((()))'
F('(())', 2, 2)
F('(())(', 3, 2)
F('(())((', 4, 2) => X : left > n
F('(())()', 3, 3) => O : add '(())()'
F('(()))', 2, 3) => X : left < right
F('()', 1, 1)
F('()(', 2, 1)
F('()((', 3, 1)
F('()(((', 4, 1) => X : left > n
F('()(()', 3, 2)
F('()(()(', 4, 2) => X : left > n
F('()(())', 3, 3) => O : add '()(())'
F('()()', 2, 2)
F('()()(', 3, 2)
F('()()((', 4, 2) => X : left > n
F('()()()', 3, 3) => O : add '()()()'
F('()())', 2, 3)
F('())', 1, 2) => X : left < right
F(')', 0, 1) => X : left < right

복잡도

위 호출 트리를 살펴보면 각 레벨에서 재귀 호출의 수가 2배씩 증가되기 때문에, 위 알고리즘은 O(2^N)의 복잡도를 가집니다.

문제 출처

공유하기