Non-Divisible Subset

문제

https://www.hackerrank.com/challenges/non-divisible-subset/problem

Non-Divisible Subset | HackerRank

 

 

풀이

알고리즘적인 부분에서 어렵지 않으나 N의 크기로 시간복잡도를 생각해야했던 문제.

배열의 값과 상관없이 값을 나눈 나머지의 값은 K <100 이하이므로 이를 이용하여 풀 수 있었다. 

 

코드

int nonDivisibleSubset(int k, vector<int> s) {
    vector<int> extra(k+1, 0); //나머지
    int result = 0;
    int size = s.size();
    
    for(int i=0; i<size; i++){
        int e = s[i]%k;
        extra[e]++;
    }
    
    //나누어떨어지는 수 하나만 포함 가능
    if(extra[0]>0){
        extra[0] = 1;
    }
    
    //중앙값은 하나만 포함 가능
    if(k%2 == 0 && extra[k/2]>0){
        extra[k/2] = 1;
    }

 
    for(int i=0; i<=(k/2); i++){
        if(extra[i]>extra[k-i]){
            result+=extra[i];
        }else{
            result+=extra[k-i];
        }
    }
    
    
    cout<< result<<endl;
    
    return result;
    
}