[Java] Level 4. 올바른 괄호의 개수

Level 4. 올바른 괄호의 개수 (출처 - 프로그래머스)

코딩테스트 연습 - 올바른 괄호의 갯수 | 프로그래머스

너무 어려운 문제였고 이를 찾아보다가 새로운 개념을 알게되었다.

카탈란 수 라는 수학적 개념이 필요한 문제였고 이를 위해 아래의 페이지를 참고했다.

https://suhak.tistory.com/77

카탈란 수(catalan number)

 

long으로 선언한 후 type casting을 해준 이유는 factorial연산 과정에서 overflow가 발생하기 때문입니다.

class Solution {
    public int solution(int n) {
        long molecular = 1;
        long denominator = 1;
        int num = 2*n;
        for (int i = 1; i <= n; i++) {
            molecular *= num--;
            denominator *= i;
        }

        return (int)(molecular / (denominator * (n+1)));
    }
}

많은 사람들이 BigInteger를 사용해서도 풀어냈길래 추가적으로 이 방법을 게시합니다.

class Solution {
    public int solution(int n) {
    	BigInteger molecular = BigInteger.ONE;
    	BigInteger denominator = BigInteger.ONE;
    	
        int num = 2*n;
        for (int i = 1; i <= n; i++) {
            molecular = molecular.multiply(BigInteger.valueOf(num--));
            denominator = denominator.multiply(BigInteger.valueOf(i));
        }
        return molecular.divide(denominator).divide(BigInteger.valueOf(n+1)).intValue();
    }
}