[Programmers] level4 - 올바른 괄호의 갯수 (Python) : 연습문제

▶올바른 괄호의 갯수 - 연습문제 (level 4)

▶문제

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

 

▶제한사항

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

 

▶출력

n	result
2	2
3	5

 

▶입출력 예 설명

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

 

▶풀이

1일때는 1개

2일때는 2개

3일때는 5개

4일때는 14개

5일때는 42개

이렇게 순서가 나열된다.

이 규칙을 설명할 수 있는게 '카탈랑 수'이다.

 

https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98

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

 

위키에서 카탈랑 수를 검색해 보았고, 거기에서 나오는 식을 사용했다.

내가 풀었다기 보다는 위키에서 문제를 풀어준 것 같다.

그대로 식을 써서 문제를 풀었더니 정답이 나왔다.

 

def factorial(n):
    if n == 1:
        return 1
    else:
        return n*factorial(n-1)


def solution(n):
    answer = 0
    a = factorial(2*n)
    b = factorial(n)**2
    answer = a/(b*(n+1))
    return answer

 

따로 효율성 검사는 없었고, 저대로 풀어서 정확성 테스트에서는 만점이 나왔다.

 

정확성 테스트

테스트 1 〉	통과 (0.00ms, 10.2MB)
테스트 2 〉	통과 (0.00ms, 10.1MB)
테스트 3 〉	통과 (0.00ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10.3MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (0.01ms, 10.1MB)
테스트 7 〉	통과 (0.01ms, 10.3MB)
테스트 8 〉	통과 (0.01ms, 10.3MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉	통과 (0.01ms, 10.3MB)
테스트 11 〉	통과 (0.01ms, 10.1MB)
테스트 12 〉	통과 (0.01ms, 10.1MB)
테스트 13 〉	통과 (0.01ms, 10.2MB)
테스트 14 〉	통과 (0.01ms, 10.2MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0