[leetcode #368] Largest Divisible Subset

Problem

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

・ answer[i] % answer[j] == 0, or
・ answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

Constraints:

・ 1 <= nums.length <= 1000
・ 1 <= nums[i] <= 2 * 10⁹
・ All the integers in nums are unique.

Idea

오늘 문제도 내 힘으로 풀지 못 했다. 몸이 피곤하면 머리도 안 돌아가는지 참 어렵다.

DFS 또는 DP를 이용해서 풀 수 있는데, DP를 이용해 푸는 법을 소개한다.

우선 input인 nums array를 정렬한다.

nums의 모든 값은 자기 자신이 나머지가 0이 되는 수이므로 dp값을 전부 1로 설정한다. 그리고 나머지가 0이 되는 수를 tracking하기 위해 index라는 array도 만든다.

nums array를 탐색하면서 해당 index보다 앞에 있는 값들 중 나머지가 0이 되는 수를 조사한다. 나머지가 0이 되는 수 중 dp값에 1을 더한 수가 현재 index의 dp값보다 큰 경우만 새로 dp값을 바꿔준다. 여기서 1은 현재 수를 의미한다. dp값이 바뀌면 tracking할 array의 값을 바꿔준 index값으로 설정한다.

현재 index보다 앞의 index를 모두 탐색한 뒤 max값보다 현재 dp값이 더 크다면 max값을 현재 dp값으로 설정하고 maxIndex도 현재 index로 설정한다.

마지막으로 maxIndex부터 index를 tracking하면서 답으로 리턴할 array에 index에 해당하는 값들을 전부 넣어주면 된다.

Solution

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        if(nums==null||nums.length==0)
            return result;

        Arrays.sort(nums);

        int[] t = new int[nums.length];
        int[] index = new int[nums.length];
        Arrays.fill(t, 1);
        Arrays.fill(index, -1);

        int max=0;
        int maxIndex=-1;

        for(int i=0; i<t.length; i++){
            for(int j=i-1; j>=0; j--){
                if(nums[i]%nums[j]==0 && t[j]+1>t[i]){
                    t[i]=t[j]+1;
                    index[i]=j;
                }
            }

            if(max<t[i]){
                max=t[i];
                maxIndex=i;
            }
        }

        int i=maxIndex;
        while(i>=0){
            result.add(nums[i]);
            i=index[i];
        }

        return result;
    }
}

Reference

https://leetcode.com/problems/largest-divisible-subset/