368. Largest Divisible Subset

• Unique한 숫자로 이루어진 배열 arr이 주어졌을 때 다음 조건을 만족하는 부분 집합 중 가장 크기가 큰 것을 구하는 문제.
• 부분 집합에서 임의의 2개 숫자 a, b를 택했을 때 a % b == 0 또는 b % a == 0을 만족한다.

• 배열을 정렬하여 풀어야 된다는 것 까지는 알았는데 부분 집합을 구성하는 방식을 고민하다가 방법이 생각나지 않아서 해답을 보았다.

• 배열을 순회하면서 현재 숫자를 기준으로 더 큰 부분 집합을 구성하는 숫자를 찾아내는 방식으로 풀어야 한다.
• 먼저 배열을 오름차순으로 정렬한다.
• 각 index 별로 부분 집합의 크기 subsetSizeList와 현재 숫자의 바로 직전 숫자에 대한 index prevIndexList를 기록한다.
• 현재 숫자 nums[i]를 기준으로 앞쪽에 있는 숫자 nums[j] (j = 0, 1, …, i - 1) 를 순회하면서 조건을 만족하는 숫자 nums[i] % nums[j] == 0 를 찾는다.
• 조건을 만족하는 숫자 중 부분 집합의 크기가 가장 크게 만드는 숫자를 선택하여 부분 집합의 크기와 해당 숫자의 index를 기록한다.
• 마지막 index maxIndex 보다 현재 index의 부분 집합의 크기가 더 크다면 현재 index를 마지막 index로 한다.

• 마지막 index부터 이전 index 배열 prevIndexList을 순회하면서 전체 부분 집합을 만들어낸다.

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
       
        int[] subsetSizeList = new int[n];
        int[] prevIndexList = new int[n];
        int maxIndex = 0;

        for(int i = 0; i < n; ++i) {
            int subsetSize = 1;
            int prevIndex = -1;
            for(int j = 0; j < i; ++j) {
                if(nums[i] % nums[j] == 0) {
                    int newSubsetSize = subsetSizeList[j] + 1;
                    if(newSubsetSize > subsetSize) {
                        subsetSize = newSubsetSize;
                        prevIndex = j;
                    }
                }
            }
            subsetSizeList[i] = subsetSize;
            prevIndexList[i] = prevIndex;
            if(subsetSize > subsetSizeList[maxIndex]) {
                maxIndex = i;
            }
        }

        List<Integer> result = new ArrayList();
        for (int i = maxIndex; i != -1; i = prevIndexList[i]) {
            result.add(nums[i]);
        }
        return result;
    }
}