[해커랭크] Non-Divisible Subset [JAVA]

문제링크 : www.hackerrank.com/challenges/non-divisible-subset/problem

Non-Divisible Subset | HackerRank

k를 9이라고 하자

어떤 수를 k로 나눈 나머지는 0~8이다

그 수들중에 1은 8을 제외하고 더했을 때 9로 나눈 나머지가 0이 되지 않는다.

마찬가지로 2도 7, 3은 6, 4는 5가 더해졌을때를 제외하고는 9로나눈 나머지가 0이 되지 않는다.

그래서 나눈 나머지가 1과8인 것들의 개수중 더 많은 것, (2,7), (3,6) .... 도 마찬가지로 더 많은 것을 골라서 집합에 포함시키면 된다.

0은 예외다. 두 수의 합이기 때문에 0과 다른 모든 수를 더해도 나머지가 0이 아닐 것 같지만

k의 배수 두 개를 더하면 k로 나눈 나머지가 0이기 때문에 k로 나눈 나머지가 0인 수가 있다면 최대 1개만 집합에 포함시킬 수 있다. k가 짝수일 때도 (k/2)인 수 두개 이상을 허용하지 않도록 한다. 

public static int nonDivisibleSubset(int k, List<Integer> s) {
        int []cnt = new int[k];
        for(int i=0;i<s.size();i++){
            cnt[s.get(i)%k]++;
        }
        int ans = 0;
        if(cnt[0]>0) ans +=1;
        if(k%2==0 && cnt[k/2] >0) ans +=1;
        for(int i=1;i<=(k-1)/2;i++){
            ans += (cnt[i]>cnt[k-i])? cnt[i]: cnt[k-i];
        }
        return ans;
    }