[LeetCode] 368. Largest Divisible Subset

😎풀이

1. nums를 오름차 순 정렬(a < b < c에서, b % a == 0이고 c % b == 0 이라면, c % a == 0임을 이용하여 최적화)
2. dp 생성(현재 인덱스에서 만들 수 있는 가장 긴 Subset 길이)
3. pre 생성(현재 인덱스의 Subset선택 이전 요소의 인덱스)
4. 2중 순회하며 최대 길이의 Subset 탐색
5. pre를 통해 요소를 탐색하며, result 반환

function largestDivisibleSubset(nums: number[]): number[] {
    const n = nums.length
    const sorted = nums.toSorted((a, b) => a - b)
    const dp = new Array(n).fill(1)
    const pre = new Array(n).fill(-1)
    let maxLen = 1
    let maxIdx = 0
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < i; j++) {
            if(sorted[i] % sorted[j] !== 0) continue
            if(dp[i] >= dp[j] + 1) continue
            dp[i] = dp[j] + 1
            pre[i] = j
        }
        if(dp[i] <= maxLen) continue
        maxLen = dp[i]
        maxIdx = i
    }
    const result = []
    let curIdx = maxIdx
    while(curIdx !== -1) {
        result.push(sorted[curIdx])
        curIdx = pre[curIdx]
    }
    return result
};