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

😀문제 설명

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

---

😁제한사항

• 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

---

😂입출력 예

n	result
2	2
3	5

---

🤣입출력 예 설명

입출력 예 #1
2개의 괄호쌍으로 [ "(())", "()()" ]의 2가지를 만들 수 있습니다.
입출력 예 #2
3개의 괄호쌍으로 [ "((()))", "(()())", "(())()", "()(())", "()()()" ]의 5가지를 만들 수 있습니다.

---

😄나의 풀이

우선 해당 문제는 Catalan Number라는 수학적 개념을 사용하여 풀 수 있으며, 공식은 (2n choose n) / (n + 1) 이다. 하지만, 이 문제를 직접 계산하는 것보다는 동적 프로그래밍을 이용해서 풀이하는 것이 더 적절하기에 DP를 활용하여 풀었음

괜찮은 설명이 있어 프로그래머스 질문하기의 faul2chris님의 글을 가져왔다.

N이 4일 때,

경우 1) ( 한개도 없음 ) x 3쌍 가짓수 ----- dp[0] * dp[3] = 1x5
경우 2) ( 1쌍 가짓수 ) x 2쌍 가짓수 ----- dp[1] * dp[2] = 1x2
경우 3) ( 2쌍 가짓수 ) x 1쌍 가짓수 ----- dp[2] * dp[1] = 2x1
경우 4) ( 3쌍 가짓수 ) x 0쌍 가짓수 ---- dp[3] * dp[0] = 5x1

　∴ dp[4] = 5 +2 +2 +5 = 14

위 글을 참고한 풀이는 아래와 같다.

function solution(n) {
    // dp 배열 초기화
    let dp = new Array(n + 1).fill(0);
    
    // 기본 케이스 설정: 0개의 괄호쌍으로 만들 수 있는 경우의 수는 1가지입니다.
    dp[0] = 1;
    
    // i가 현재 사용할 괄호쌍의 개수입니다.
    for(let i = 1; i <= n; i++) {
        // j는 왼쪽 괄호에서 시작해서 오른쪽 괄호까지 짝을 지어줍니다.
        // 쉽게 말해, dp[0] + dp[1] + ... dp[i-1] 을 dp[i] 에 담는 것
        for(let j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }
    
    return dp[n];   // n개의 괄호쌍으로 만들 수 있는 올바른 문자열 갯수 반환
}