[LeetCode] 368. Largest Divisible Subset

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

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Large Divisible Subset

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

 

문제

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.

 

양의정수집합 nums가 주어진다.

집합의 요소들이 서로 약수와 배수 관계가 되는 가장 큰 부분집합을 구하시오.

여러 답이 있다면, 하나만 반환하시오.

 

풀이

우선, 배열을 정렬한다.

dp배열을 만들어서 dp[i]에는 i번째요소를 마지막으로 넣은 유효한 부분집합을 저장시킨다.

 

배열을 순차적으로 순회하면서, 이전 인덱스들과 비교해가며 이전 인덱스가 현재 인덱스의 약수가 되고, 이전 dp의크기가 현재보다 크다면, dp[i]에 dp[j]를 넣는다.

j가 i의 약수라면(단, j < i), dp[j]에 있는 수들 모두 dp[i]의 약수들이다.

이것이 정렬을 해놓은 이유이다. 중간에 규칙을 깨는 변수를 없애기 위해 정렬을 한 것이다.

 

이전 인덱스들과의 비교가 끝나면 dp[i]의 끝에 nums[i]를 넣는다.

 

dp배열을 순회하면서 가장 큰 부분집합을 구해서 반환하면 된다.

 

 

코드

C++

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        const int n = nums.size();
        vector<vector<int>> dp(n, vector<int>());
        sort(nums.begin(), nums.end());

        for(int i = 0; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
                if(nums[i] % nums[j] == 0 && dp[i].size() < dp[j].size()) {
                    dp[i] = dp[j];
                }
            }
            dp[i].push_back(nums[i]);
        }

        int maxIdx = 0;
        for(int i = 0; i < n; i++) {
            if(dp[maxIdx].size() < dp[i].size()) maxIdx = i;
        }

        return dp[maxIdx];
    }
};

Go

func largestDivisibleSubset(nums []int) []int {
    n := len(nums)
    dp := make([][]int, n)
    sort.Ints(nums)

    for i := 0; i < n; i++ {
        for j := i - 1; j >= 0; j-- {
            if nums[i]%nums[j] == 0 && len(dp[i]) < len(dp[j]) {
                dp[i] = append([]int{}, dp[j]...)
            }
        }
        dp[i] = append(dp[i], nums[i])
    }

    maxIdx := 0
    for i, v := range dp {
        if len(v) > len(dp[maxIdx]) {
            maxIdx = i
        }
    }

    return dp[maxIdx]
}