[프로그래머스] 12929 올바른 괄호의 갯수 - JAVA (카탈란 수)

[프로그래머스] 12929 올바른 괄호의 갯수 - JAVA

문제

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

 

문제 분석

조건

`n`이 주어질 때 만들 수 있는 올바른 괄호의 수를 구하는 문제이다. 올바른 괄호란 `()`, `(())`, `()()` 등 올바르게 모두 닫힌 괄호를 의미한다.

카탈란 수(Catalan Number)란?

이 문제는 카탈란 수를 이용하여 푸는 문제이다. 코드의 풀이보다는 이 문제에 활용되는 카탈란 수에 대해 정리하는 것이 더 중요한 것 같다. 우선 이 문제를 바탕으로 카탈란 수를 먼저 이해해 보자면,

n=1일 경우는 `()`으로 1가지 방법이 존재한다.
n=2: `()()`, `(())`으로 2가지가 존재하는데, 이를 그림으로 나타내보면 아래와 같다.

위 사진으로 본다면 n=1일 때 노란색 괄호가 n=2일 때 파란색 괄호를 기준으로 오른쪽이나 안쪽으로 들어가 있음을 확인할 수 있다. 이를 n=3일 때로 확장해 본다면

이렇게 나타낼 수 있게 된다. 색을 기준으로 본다면 n=3일 때 초록색 괄호를 기준으로 첫 번째 줄에선 오른쪽에 n=2일 때가 배치되어 있음을 알 수 있다. 
두 번째 줄에서는 초록색 괄호 안에 n=1, 괄호 오른쪽에 n=1.
마지막 줄에선 초록색 괄호 안에 n=2인 모습이 들어있다. 이를 풀어서 작성해 본다면

이렇게 된다. 즉 n쌍으로 만들 수 있는 경우의 수는 `i`쌍을 괄호 안쪽에 넣고, `n-1-i`쌍을 괄호 오른쪽에 배치하는 값인 것이다. dp [3]을 식으로 나타내본다면

`dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0]`이 되고, 이를 점화식으로 표현하면 아래와 같은 코드로 답을 구할 수 있다. 

이와 같이 카탈란 수는 특정 조건을 만족하는 조합의 수를 구할 때 사용되는 수열이다. 올바른 괄호 문제 말고도 카탈란 수를 이용하는 대표적인 문제들이 있는데, 이진트리 구조의 수, 스택으로 반들 수 있는 순열의 수 등이 있다. 이러한 문제들은 공통적으로 재귀적 구조를 가지며, 정해진 규칙을 지키는 조합만을 허용한다는 특징이 있다. 예를 들어 괄호나 스택 문제에서는 왼쪽이 없는데 오른쪽이 존재할 수 없고, 왼쪽과 오른쪽의 총개수가 맞아야 유효한 조합이 된다.

중요한 점은, 문제를 부분으로 나누었을 때도 같은 규칙이 계속 유지되어야 한다는 점이다. 즉, 단순한 조합 문제가 아니라 순서를 고려하면서도 구조적인 조건을 만족해야 하는 경우, 카탈란 수가 유효하게 적용되는 것이다.

코드

class Solution {
    public int solution(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

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