Largest Divisible Subset

문제 설명

• 서로 다른 양의 정수로 이루어진 배열 nums가 주어집니다.
• 다음 조건을 만족하는 가장 큰 부분집합 answer을 반환해야 합니다.
  • 부분집합 내의 모든 쌍 (answer[i], answer[j])에 대해, answer[i] % answer[j] === 0 또는 answer[j] % answer[i] === 0 이어야 합니다.
  • 즉, 한 숫자가 다른 숫자를 나누거나, 나누어져야 합니다.
• 여러 개의 답이 있다면, 아무거나 하나를 반환하면 됩니다.

문제 풀이

Dynamic Programming & Sorting

1. nums 정렬
   • 작은 수부터 차례대로 확인하기 위해 nums를 오름차순으로 정렬합니다.
   • 이렇게 정렬하면, 뒤에 나오는 수가 앞의 수로 나누어지는지를 쉽게 판단할 수 있습니다.
2. dp와 prev 배열 초기화
   • dp[i]: nums[i]로 끝나는 가장 긴 부분집합의 크기
   • prev[i]: nums[i] 이전에 연결된 숫자의 인덱스 (부분집합 경로 추적용)
3. dp 및 prev 배열 채우기
   • 모든 i < j 쌍에 대해 nums[j] % nums[i] === 0이면, nums[j]는 nums[i]와 배수 관계이므로 부분집합에 포함될 수 있습니다.
   • 이때 dp[j] < dp[i] + 1인 경우 dp[j]를 갱신하고, prev[j]에 i를 저장합니다.
   • 이 과정을 통해 각 원소별로 만들 수 있는 가장 긴 부분집합의 크기와 경로를 기록합니다.
   • maxIndex에는 가장 긴 부분집합의 끝 인덱스를 저장합니다.
4. 결과 부분집합 구성 및 반환
   • prev 배열을 사용해 maxIndex부터 거슬러 올라가며 부분집합을 역추적합니다.
   • 추적한 원소들을 answer 배열에 추가한 후, 이를 반환합니다.

export function largestDivisibleSubset(nums: number[]): number[] {
  nums.sort((a, b) => a - b);
 
  const n = nums.length;
  const dp = new Array<number>(n).fill(1);
  const prev = new Array<number>(n).fill(-1);
 
  let maxIndex = 0;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] % nums[j] === 0 && dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
        prev[i] = j;
      }
    }
    if (dp[maxIndex] < dp[i]) {
      maxIndex = i;
    }
  }
 
  const answer: number[] = [];
  let currentIndex = maxIndex;
  while (currentIndex !== -1) {
    answer.push(nums[currentIndex]);
    currentIndex = prev[currentIndex];
  }
  return answer;
}

복잡도

• 시간 복잡도: $O(n^2)$
• 공간 복잡도: $O(n)$