[Programmers] 프로그래머스 파이썬 > 올바른 괄호의 갯수

문제. 프로그래머스 올바른 괄호의 갯수

---

문제 설명

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

 

제한사항

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

---

입출력 예

n	result
2	2
3	5

 

입출력 예 설명

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

 

출처 : 프로그래머스 올바른 괄호의 갯수

코딩테스트 연습 - 올바른 괄호의 갯수

---

나의 풀이 in Python

#[Programmers] 프로그래머스 파이썬 > 올바른 괄호의 갯수
# 카탈란 수 구현
import math
def solution(n):
    return math.factorial(2*n) // (math.factorial(n) * math.factorial(n+1))

예시

괄호에 대한 경우의 수를 다 잡기에는 시간 초과로 코드가 안돌아갈 것 같아서 예시를 생각해봤습니다. n이 5까지의 값을 토대로 점화식을 만들어보려고 했지만, 감이 도저히 안와서 다른 고수분들의 풀이를 참고했습니다.

 

수학적으로 유명한 수인 카탈랑 수를 참고하면 풀 수 있는 문제입니다.

참고 : 카탈랑 수

카탈랑 수 - 위키백과, 우리 모두의 백과사전

조합론에서의 개수 세기 문제 가운데 많은 것들이 카탈랑 수를 그 해로 갖기에 알아두면 좋은 문제라고 생각합니다.