C++에서 가장 큰 나눌 수 있는 부분집합

고유한 양의 정수 집합이 있다고 가정하고 이 부분 집합의 (Si, Sj)와 같은 모든 요소 쌍이 Si mod Sj =0 또는 Sj mod Si =0을 충족하도록 가장 큰 부분 집합을 찾아야 합니다.

따라서 입력이 [1,2,3]과 같으면 가능한 결과는 [1,2] 또는 [1,3]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 배열 ret 생성, 끝점 설정 :=0, retLen :=1, n :=숫자 크기

• n이 0이면 빈 집합을 반환합니다.

• 숫자 배열 정렬

• 크기가 n인 두 개의 배열 len과 par를 만들고 len을 1로 초기화하고 par를 0으로 초기화

• 범위 1에서 n – 1까지의 i에 대해

  • par[i] :=i

  • 범위 0에서 i – 1의 j에 대해

    • nums[i] mod nums[j] =0이고 len[j] + 1> len[i]이면

      • 렌[i] :=렌[j] + 1

      • par[i] :=j

  • len[j]> retLen이면 retLen :=len[i]이고 끝점 :=i

• ret에 nums[endPoint] 삽입

• 끝점이 par[endPoint]

  와 같지 않은 동안

  • 끝점 :=par[endPoint]

  • ret에 nums[endPoint] 삽입

• ret 목록을 뒤집고 ret를 반환합니다.

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> largestDivisibleSubset(vector<int>& nums) {
      vector <int> ret;
      int endPoint = 0;
      int retLen = 1;
      int n = nums.size();
      if(!n) return {};
      sort(nums.begin(), nums.end());
      vector <int> len(n, 1);
      vector <int> par(n, 0);
      for(int i = 1; i < n; i++){
         par[i] = i;
         for(int j = 0; j < i; j++){
            if(nums[i] % nums[j] == 0 && len[j] + 1 > len[i]){
               len[i] = len[j] + 1;
               par[i] = j;
            }
         }
         if(len[i] > retLen){
            retLen = len[i];
            endPoint = i;
         }
      }
      ret.push_back(nums[endPoint]);
      while(endPoint != par[endPoint]){
         endPoint = par[endPoint];
         ret.push_back(nums[endPoint]);
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3};
   print_vector(ob.largestDivisibleSubset(v));
}

입력

[1,2,3]

출력

[1, 2, ]