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

문제 설명

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

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

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

 

제한사항

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

입출력 예

n / result

2	2
3	5

입출력 예 설명

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

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

 

 

---

풀이

- 괄호 예시 보려고 검색해봤더니 카탈란 수라길래 공부해서 공식 적용시킴

 

▼

우리는 n쌍의 괄호가 만든 모든 가능한 모든 괄호 형태의 개수를 Cn 이라 쓰고 이 를 카타란수(Catalan Numbers)라 부른다. 우리는 C0 = 0으로 정의하였다. 따라서 처음 4개의 카타란수는 다음과 같다
C0 = 1, C1 = 1, C2 = 2, C3 = 5

[C4를 구하는 방법]

전제 : 왼쪽 끝에 한 쌍의 () 괄호를 두고, 이 괄호의 안과 밖을 생각해서 계산

1단계. 왼쪽 끝 한 쌍의 괄호 () 안에는 없고, 오른쪽에 괄호 3쌍 두기
() {3쌍의 괄호}   = 경우의 수 C0*C3

2단계. 왼쪽 끝 한 쌍의 괄호 () 안에 1쌍의 괄호를 넣고, 오른쪽에 2쌍 두기
({1쌍의 괄호}) {2쌍의 괄호}   = 경우의 수 C1*C2

3단계. 왼쪽 끝 한 쌍의 괄호 () 안에 2쌍의 괄호를 넣고, 오른쪽에 1쌍 두기
({2쌍의 괄호}) {1쌍의 괄호} = 경우의 수 C2*C1

4단계. 왼쪽 끝 한 쌍의 괄호 () 안에 3쌍의 괄호를 넣고, 오른쪽에 0쌍 두기
({3쌍의 괄호})  = 경우의 수 C3*C0


결론적으로 C4 = C0*C3 + C1*C2 + C2*C1 + C3*C0 = 5+2+2+5 = 14

 

 

- 위에 카탈란수 식을 더 공식화 해놓은 게 있었는데, 어려워서 그냥 위에 방법 토대로 작성함

 

 

class Solution {
    public int solution(int n) {       
        int[] dp = new int[n+1];
        
        dp[0] = 1;
        dp[1] = 1;
        
        for(int i = 2; i<=n; i++){ 
            for(int j=1; j<=i; j++){
                dp[i] += dp[i-j] * dp[j-1]; 
            }
        }
  
        return dp[n];
    }
}

 

 

 

*카탈란 수 참고 : https://suhak.tistory.com/77