[프로그래머스] 올바른 괄호 개수 (Python)

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

프로그래머스

Status : Solved

Time : 00:46:18

 

---

 

 

문제 설명

 

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

 

 

입력 및 출력

 

제한사항

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

 

입출력 예

n	result
2	2
3	5

 

 

---

 

 

풀이

 

n번째 괄호의 개수를 구할 때 이전 1 ... n-1번째 괄호의 개수가 영향을 미칠 수 있다는 점을 고려하면, DP로 문제 접근을 해 보아야 한다는 걸 알 수 있다. 다만 DP는 이전의 상태를 어떻게 정의내려야한다는 건지 정확히 파악해야 한다는 전제조건이 있다... 

 

이러한 괄호 개수 구하기는 카탈랑 수열에 포함된다고 한다.(오늘도 하나 배웠다!)

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

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

 

우선 카탈랑 수에 대해 말하기 전에, 본 문제에 대해 분석해 보자.

n번째 올바른 괄호의 개수를 n-1번째 괄호의 개수에서 도출하는 방법부터 생각해 보자. 우선 n = 3일때를 생각해 본다면, 2개의 괄호쌍의 개수는 ()(), (()) 가 될 것이다.

총 괄호의 개수가 n이라면, 1~n-1의 케이스의 조합으로 나타낼 수 있다는 사실은 자명하다. 여기서 우리는 직관적으로, n-1개의 괄호 양 쪽에 괄호를 세우거나 ((())), (()()) 혹은 왼쪽, 오른쪽에 괄호를 세우는 경우 ()(()), (())(), ()()()를 생각해 볼 수 있을 것이다. 실제 n=3일때 역시 총 개수는 5가 되므로 옳은 경우이다. 하지만 n이 4일때는? (())(())와 같은 케이스는 위 알고리즘으로 해결할 수 없다. n=2일때의 경우 (())를 이어붙인 케이스이기 때문이다. 또한 중복 역시 걸러낼 수 없는데, ()()() + () 의 결과와 () + ()()()의 결과는 동일하기 때문이다. 

 

n개의 괄호로 나타낼 수 있는 개수를 Cn이라고 둔다면, Cn = f(C1, Cn-1) + f(C2, Cn-2) ... f(Cn-1, C1)꼴로 나타나게 된다.  여기서 함수 f를 왼쪽 Ck 양쪽에 괄호를 세우는 경우의 수로 정의해보자. 이 때, 괄호 하나가 추가되는 꼴이므로 왼쪽의 idx를 재조정하고 고려해야 항을 더 추가한다. 바뀐 식은 다음과 같다 :

Cn = f(C0, Cn-1) + f(C1, Cn-2) + ... + f(Cn-1, C0)

여기서 우리는 이 함수 f를 찾아내기만 하면 된다. 다시 n = 3인 경우로 돌아가면...

• C0 x C2 : ( + '빈 공간' + ) + ()() = ()()(), ( + '빈 공간' + ) + (()) = ()(()), 1 x 2 = 2
• C1 x C1 : ( + () + ) + () = (())(), 1 x 1 = 1
• C2 X C0 : ( + ()() + ) + '빈 공간' = (()()), ( + (()) + ) + '빈 공간' = ((())), 2 x 1 = 2 

으로 모든 경우의 수를 고려할 수 있다는 사실을 만족한다. 중복 처리, 1 .. n-1의 경우의 수를 모두 고려한다는 제약 조건 역시 동일하다. 여기서 초기항 C0이 등장하였는데, 빈 공간이긴 하지만 곱셈 연산을 위해 1로 초기화한다는 점을 고려하자. 따라서 위 식은 최종적으로 다음과 같아진다.

Cn = C0*Cn-1 + C1*Cn-1 + .... + Cn-1*C0

이렇게 정의되는 수열이 카탈란 수열이 된다. 카탈란 수열은 이외에도 계산 순서 구하기, 이진 트리, 삼각형 개수 구하기 등 개수를 구하는 많은 문제의 해답이 될 수 있다고 한다!  아래 블로그를 참조하였음을 밝혀 둔다.

https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.4-%EC%98%AC%EB%B0%94%EB%A5%B8-%EA%B4%84%ED%98%B8-%EA%B0%AF%EC%88%98-JS

[프로그래머스] LV.4 올바른 괄호 갯수 (JS)

 

 

 

풀이 코드

def solution(n):
    dp = [0]*(n+1)
    dp[0] = 1
    for i in range(1, n+1) :
        for j in range(i):
            dp[i] += dp[j] * dp[i-j-1]
            
    return dp[n]