LeetCode: 96번 (Unique Binary Search Trees) [JAVA]

문제 링크

https://leetcode.com/problems/unique-binary-search-trees/

Unique Binary Search Trees - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. dp를 사용하기 위한 int 배열 생성, dp[0]을 1로 초기화
2. 숫자 1부터 n까지, 다음과 같은 반복문을 수행 (임시 변수 i)
   1) 0부터 i까지(임시 변수 j), dp[i] += dp[j] * dp[i - 1 - j]
3. 이후 dp[n]을 반환

 직전 문제인 Unique Binary Search Trees II와 거의 동일한 문제이지만, 모든 트리를 일일히 만들어야 했던 이전과 달리 단순히 개수만 카운트하면 되기 때문에 훨씬 쉽고 간단히 풀 수 있다.
 1부터 n까지의 숫자들로 구성된 이진 탐색 트리는, 루트 노드로 삼을 숫자 한 개를 제외하고, 양쪽을 특정 j개와, 전체 n개에서 j개와 루트 노드에 사용한 숫자 1개를 뺀 값으로 만들 수 있는 서브 트리들의 조합으로 만들어낼 수 있다. 즉 전체 이진트리에 사용할 수 있는 숫자의 개수를 n이라 하면, 만들 수 있는 이진 탐색 트리의 개수는, j개일 때의 이진 탐색 트리 개수 * n - 1 - j개일 때의 이진 탐색 트리 개수의 곱이다. 이 때 j가 0부터 n - 1까지 모두 들어갈 수 있기 때문에, 모든 누적값을 더하면 된다.
 그리고 n개의 이진 탐색 트리를 개수를 구할 때, 그 이하 숫자들의 이진 탐색 트리 개수가 모두 필요로 하기 때문에, 이를 해결하기 위해선 바텀업 방식의 dp를 사용해야 한다. 우선 dp를 위한 int 배열을 생성 후, 노드가 0개면 그 때의 트리 개수는 1개기 때문에 dp[0]을 1로 초기화 한다. 이후엔 1부터 n까지, 임시 변수 i를 바탕으로 반복문을 돌며 해당 dp[i]의 값을 채운다. 임시 변수 j를 두고 0부터 i - 1까지 반복문을 통해, dp[i] += dp[j] * dp[i - 1 - j]를 계산하여 전체 숫자가 i개 일 때 이진트리의 개수를 카운트한다.
 이후 해당 이중 for문을 통해 바텀업 방식의 dp를 모두 연산하고 나면, dp[n]의 값을 단순히 반환하면 된다.

 

class Solution {
    int[] dp;

    public int numTrees(int n) {
        dp = new int[n + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {//bottom-up dp
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }

        return dp[n];
    }
}

결과