[프로그래머스] 올바른 괄호의 갯수 - DFS부터 카탈란 수 풀이까지

https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

이 문제는 input으로 괄호쌍의 개수가 들어오고, output으로 (()), ()()처럼 올바른 괄호의 개수를 출력하는 문제이다.

 

아마 반대의 문제를 많이 접해봤을 것이다.

예를 들면 괄호 문자열이 주어지고, 그게 올바르게 닫힌 괄호인지 검증하는 문제.

이는 문자열을 순회하면서 닫힌 괄호 ')' 의 개수가 열린 괄호 '(' 의 개수를 초과하지 않는지 검사하고, 마지막에 두 괄호의 개수가 같은지 확인하면 된다.

 

1. DFS

나는 그 아이디어를 차용해서, 가장 먼저 dfs 방법으로 풀어봤다.

루트인 열린 괄호부터 시작해서, 그 다음에 각각 열린 괄호와 닫힌 괄호인 경우를 탐색하는 방식이다.

 

다만, 열린 괄호를 탐색할 수 있는 조건은 열린 괄호의 개수가 괄호쌍의 개수보다 적을 때만 가능하고,

닫힌 괄호를 탐색할 수 있는 조건은 닫힌 괄호의 개수가 열린 괄호의 개수보다 적을 때만 가능하다.

 

int search(int left, int right, int n) {
    if (left == n && right == n) {
        return 1;
    }

    int cnt = 0;

    if (left < n) {
        cnt += search(left + 1, right, n);
    }

    if (right < left) {
        cnt += search(left, right + 1, n);
    }

    return cnt;
}

int solution(int n) {
    int answer = search(0, 0, n);
    return answer;
}

 

괄호쌍의 개수를 N이라고 할 때, 만들어야 하는 문자열의 길이는 2N이다. 각 자리마다 '(' 또는 ')'를 선택할 수 있으므로, 단순한 완전 탐색의 상한은 O(2^(2N)) = O(4^N)이다.

 

가지치기를 하기 때문에 좀 더 작겠지만, 4^N에서 다항식으로 나눈 정도라서 여전히 지수적인 증가를 하게 된다.

 

2. 카탈란 수

그래서 개선된 방법은 카탈란 수를 이용하는 방식이다.

(A)B
괄호쌍이 i개인 올바른 괄호 문자열은 항상 (A)B 형태로 나눌 수 있다.
여기서 바깥 괄호 한 쌍을 제외하면 남은 괄호쌍은 i - 1개이고, 이를 A와 B가 각각 j개, i - 1 - j개씩 나누어 가진다.

 

예시를 들어보자.

 

1개 괄호쌍으로 만들 수 있는 전체 개수는 () -> 1개.

이걸 벡터 v[1]에 저장한다.

 

그럼 2개 괄호쌍이 있을 때, 2번째 괄호쌍은 A를 감싸며 사용되었고,

가능한 a, b의 경우의 수는 다음과 같다.

a	b	v[a] * v[b]
0	1	1 * 1 = 1
1	0	1 * 1 = 1

 

(v[0]은 초기에 1로 설정해야 v[1]을 만들 수 있다.)

그러므로 v[2]는 1+1=2가 된다.

 

#include <vector>

using namespace std;

int solution(int n) {
    vector<int> v(n + 1, 0);
    v[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i - 1; j++) {
            v[i] += v[j] * v[i - j - 1];
        }
    }
    
    return v[n];
}

 

이 방식의 시간 복잡도는 노드가 N개라고 할 때, 1+2+...+N=N(N+1)/2, 즉 O(N^2)이다.

첫 번째 방법보다 더 작은 값을 가진다.

카탈란 수 점화식을 이용한 bottom-up DP 방식으로, 이전에 계산한 괄호쌍 개수의 결과를 재사용하면 훨씬 쉽고 빠르게 풀 수 있음을 배웠다.