[Python 걸음마] LeetCode 368. Largest Divisible Subset 문제 풀이

문제

• 링크: https://leetcode.com/problems/largest-divisible-subset/description/?envType=daily-question&envId=2024-07-06
• 입력: distinct 양의 정수 리스트
• 조건: 리스트에 들어 있는 모든 정수 쌍(pair)이 나누어 떨어져야 한다.  -> a % b == 0 이거나 b % a ==0 둘 중 하나의 조건만 만족하면 됨.
• 출력: 위 조건을 만족하는 가장 큰 사이즈의 리스트

 

풀이 방법

• 일단 정렬
• 예: 입력이 [1, 3, 5, 6, 8, 10, 12]라고 하자
• 각 값에 대해서 <조건에 맞는 최대 개수, 최대 값을 가지는 index>를 저장해 보자. index는 0부터 시작
• nums[i] % nums [j] == 0이면 count++하면 된다.
  • 이중 포문으로 처리한다고 했을 때, 자기 자신과 만나면 패스. 정렬해서 그 이후로는 무조건 자기보다 숫자가 커지기 때문

i \ j	1	3	5	6	8	10	12	<최대 개수, 인덱스>
1	0	0	0	0	0	0	0	<0, 0>
3	1	0	0	0	0	0	0	<1, 0>
5	1	0	0	0	0	0	0	<1, 0>
6	1	2	0	0	0	0	0	<2, 1>
8	1	0	0	0	0	0	0	<1, 0>
10	1	0	2	0	0	0	0	<2, 2>
12	1	2	0	3	0	0	0	<3, 3>

 

• 예제를 보면 12(index: 6)가 조건에 맞는 element 개수가 가장 많다. 
  • 12는 6을 포함한다(12%6==0). 
  • 이 말은 즉, 6이 포함하는 수는 12에 포함된다는 것이다. 
  • 그렇다면 12가 가지는 element 개수는 (6이 가지는 element 개수 +1)을 하면 됨.
  • 즉, 12가 가지는 element 중 "최대 개수" 값이 큰 element의 최대 개수 +1을 해주면 12의 최대 개수가 나오고, 그 element의 index를 저장해 주면 된다.
• 이런 식으로 숫자별 최대 개수와 인덱스를 모두 구했다면, 정답 리스트를 생성하기만 하면 된다.
• 먼저 최대 개수가 가장 큰 값을 고른다 -> 12(index: 6) - <3, 3>
  • 12의 index는 3 -> 6(index: 3)
  • 6의 index는 1 -> 3(index: 1)
  • 3의 index는 0 -> 1(index: 0)
  • 이렇게 쭉 따라가면 {12, 6, 3, 1}이라는 결과가 나오게 된다.

 

코드

class Solution(object):

    class MaxElement:
        def apply(self, max_count, index):
            if self.max_count <= max_count:
                self.max_count = max_count
                self.index = index

        def __init__(self, max_count, index):
            self.max_count = max_count
            self.index = index

    def largestDivisibleSubset(self, nums):
        elements = []
        nums.sort()
        final_max_element = self.MaxElement(
            0, 0
        )  # 가장 많은 엘리먼트를 가지는 숫자의 엘리머트 수와 index
        length = len(nums)
        for i in range(length):
            element = self.MaxElement(0, 0)
            for j in range(length):
                if nums[i] == nums[j]:
                    break
                if nums[i] % nums[j] == 0:
                    count = elements[j].max_count + 1
                    element.apply(count, j)

            elements.append(element)
            final_max_element.apply(element.max_count, j)

        result = []
        next_idx = final_max_element.index
        for i in range(final_max_element.max_count + 1):
            result.append(nums[next_idx])
            next_idx = elements[next_idx].index

        return result