Leetcode 368. Largest Divisible Subset

문제

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가 주어진다, 이 nums로 아래의 조건을 만족하는 부분배열을 만들었을때
최대 길이의 부분배열을 리턴하시오, 여러개가 있으면 그중 아무거나 리턴하면 된다.

• 조건
  • 모든 배열의 원소들에 대해 쌍을 만들었을때, 그 쌍은 반드시 한 수가 한 수를 나눌수 있어야 한다.

예시

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

제한

• $1 <= nums.length <= 1000$
• $1 <= nums[i] <= 2 * 10^9$
• 배열의 모든 숫자는 유일하다.

풀이법

1. search(i) 함수의 뜻은 nums[i]를 포함하는 조건에 부합하는 가장 큰 부분배열을 리턴한다는 의미이다.
2. nums를 정렬한 뒤 search하면 부분배열에서 마지막에 들어가는 숫자 ( 가장 큰 숫자 ) 가 다음 큰 nums의 숫자에 나눠지면 나머지는 전부 나눠지기에 무조건 부분배열에 포함될수 있다.
3. 이를 이용해 구한다.

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()

        cache = {}

        def search(i: int):
            if i == len(nums):
                return []

            if i in cache:
                return cache[i]
			
            // search(i)는 nums[i] 로 시작하는 큰 부분배열이기에 기본으로 포함한다.
            res = [nums[i]]

            for j in range(i + 1, len(nums)):
            // nums[i]가 nums[j]를 나눌수 있으면 이를 포함한다는 의미.
                if nums[j] % nums[i] == 0:
                	// nums[j]를 포함한다.
                    tmp = [nums[i]] + search(j)
                    // 더 긴 배열인지 확인후 변경한다.
                    if len(tmp) > len(res):
                        res = tmp

            cache[i] = res

            return res

		// search(i)는 i부터 시작하는것을 확인하기에 다른 index로 부터 시작하는것도 전부 검사해야 한다.
        res = []
        for i in range(len(nums)):
            tmp = search(i)
            if len(res) < len(tmp):
                res = tmp

        return res

후기

• 다음에 한번 더 풀어봐야지...