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

문제

 

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

 

제한 사항

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

 

---

풀이

 

보자마자 이게 왜 Level 4 문제지? 했다가 14번 테스트 케이스 때문에 골머리 앓았던 문제다. 처음 접근할 때 괄호 쌍이 나올 수 있는 경우의 수를 전부 백트래킹으로 탐색했다. 1 ~ 13번 테스트 케이스까지는 PASS했는데, 14번이 시간 초과가 났다. 검색해보니까 카탈란 수(Catalan number)라는 알고리즘을 사용하더라.

 

 

■ 카탈란 수(Catalan number)

• 조합론에서 이진 트리의 수 따위를 셀 때 등장하는 수열
• $ C_{n} = \frac{2n!}{{(n+1)!}{n!}} $ 로 정의된다.

 

카탈란 수의 정의를 알더라도 단순하게 접근하면 n = 14일 때, 분자가 28!(long의 범위를 벗어나는 수)이 된다. 그래서 분자를 2n!을 (n+1)!로 미리 나눈 수 (n+2) x (n+3) x (n+4) x ··· ··· x (2n-1)! x (2n)!으로 두고, n!를 나누어줬다.

 

public class Solution {

    public int solution(int n) {
        if(n <= 1) return 1;

        long x = 1, y = 1;
        for(int i=2; i<=n*2; i++) {
            if(i < n + 1) y *= i;
            else if(i > n + 1) x *= i;
        }
        return (int) (x / y);
    }
}

 

p.s) 또 다른 풀이로 다이나믹 프로그래밍으로도 점화식을 구해서 푸는 방법이 있더라.