LeetCode - 22. Generate Parentheses

목차

문제 개요

난이도 - MEDIUM 사용 언어 - C++

정수 n이 주어지면 n개의 괄호로 이루어지는 모든 조합을 반환해야 합니다.

예를 들어 n = 1이라면 ["()"]이며,

n = 2이라면 ["(())", "()()"],

그리고 n = 3이라면 ["((()))","(()())","(())()","()(())","()()()"]를 반환해야 합니다.

문제 - LeetCode - 22. Generate Parentheses

풀이

My Solutions(Github)

Solution 1 - Brute force

첫 번째 풀이 방법은 Brute force(무차별 대입)입니다. 이 방법은 풀이가 간단하므로 시간 복잡도 Big-O만 계산하고 넘어가겠습니다.

먼저 n = 3인 경우에 대해서 모든 조합에 대한 트리를 구성해보겠습니다.

조합이 열린 괄호, 닫힌 괄호 두 가지이기 때문에 완전 이진 트리가 형성되었습니다. 단순히 Brute force를 한다면 트리를 탐색하면서 생기는 모든 조합이 탐색될 것입니다.

그렇다면 완전 이진 트리의 노드 수만큼 순회가 발생하게 됩니다. 완전 이진 트리는 2^h-1개의 노드를 가질 수 있습니다(여기서 h는 트리의 높이).

그러므로 n=3일 때 트리의 높이는 h=4이므로 최소

$O(2^n)$

Solution 2 - Backtracking

이제 Backtracking 기법을 사용해, Brute force 방법에서 적절한 괄호 쌍이 형성되지 않는 경로는 탐색하지 않도록 최적화를 시도해보겠습니다.

별도의 open, close 변수를 선언합니다. open 변수는 현재 열린 괄호의 수, close 변수는 닫힌 괄호의 수를 나타냅니다.

정상적으로 열리고 닫힌 괄호쌍이 형성될 때는 항상 열린 괄호가 먼저 등장하고 닫힌 괄호가 나중에 등장해야 합니다.

그리고 이 문제에서는 괄호의 수인 n이라는 값이 주어지므로, 열린 괄호의 수가 n개를 넘어서는 안 됩니다. n개를 넘어서는 순간 n개 이상의 괄호가 형성되기 때문입니다.

이런 식으로 현재 열린 괄호의 수보다 닫힌 괄호의 수가 커지는 경우는 탐색하지 않고 다시 돌아갑니다.

또한 열린 괄호의 수가 n보다 커지는 경우도 모두 제외합니다.

코드로 이를 구현해보겠습니다.

void generate(int n, int open, int close, string s, vector<string>& out) {...}

Backtracking으로 구현하기 위해 별도의 재귀 함수를 선언합니다. 물론 일반적인 순회문으로도 충분히 구현할 수 있습니다.

open, close 변수는 앞서 설명했으며, n은 괄호의 수, s는 현재까지 탐색된 괄호의 조합 문자열, out은 조합된 괄호의 출력입니다.

if (open < n)
{
    generate(n, open + 1, close, s + '(', out);
}

만약 열린 괄호의 수가 최대 괄호 개수보다 적다면 새로운 괄호를 열고 탐색을 계속합니다.

if (close < open)
{
    generate(n, open, close + 1, s + ')', out);
}

현재 닫힌 괄호의 수가 열린 괄호의 수보다 적다면 괄호를 하나 닫고 계속 탐색합니다.

if (s.length() == n * 2)
{
    out.push_back(s);
}

지금까지 조합된 괄호 문자열의 길이가 n*2라면 출력 배열에 삽입합니다. n * 2인 이유는 간단합니다. 입력 n은 괄호 쌍의 개수를 나타내고, 괄호 하나의 쌍은 문자 2개로 이루어지기 때문에, 문자열의 길이가 n * 2라면 n개의 괄호쌍이 모두 조합된 것이므로 출력 배열에 삽입하면 됩니다.

이렇게 구현이 끝났습니다. 실질적인 구현 코드는 10줄가량이 채 되지 않습니다.

항상 느끼지만, 몇십 분 넘게 고민해도 구현 코드는 몇 줄 되지 않을 때마다 조금 허탈하면서도 뿌듯한 기분이 듭니다.

제출 결과

제출 표본이 적기 때문에 100%는 큰 의미가 없지만, 실행 속도가 0ms로 나왔으니 충분히 좋은 알고리즘을 구현한 것 같습니다.

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;

        generate(n, 0, 0, "", result);

        return result;
    }

    void generate(int n, int open, int close, string s, vector<string>& out)
    {
        if (s.length() == n * 2)
        {
            out.push_back(s);
        }

        if (open < n)
        {
            generate(n, open + 1, close, s + '(', out);
        }

        if (close < open)
        {
            generate(n, open, close + 1, s + ')', out);
        }
    }
};