[해커랭크] non-divisible-subset

문제

---

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

Non-Divisible Subset | HackerRank

Given a set of distinct integers, print the size of a maximal subset of  where the sum of any 2 numbers in  is not evenly divisible by k.

 

 

풀이

---

부분 집합 중에서 두개의 합이 항상 k 로 나눠지면 안되는 문제다.

 

n < 10 ^ 5 기 때문에 모든 부분집합을 구해서 푸는 방법은 불가능하다.

 

두개의 합이 k 로 나누어 떨어지기 위해서는 나머지의 합을 보면 알 수 있었다.

 

3가지 경우의 수가 존재한다.

1.  수가 k 로 나누어 떨어지는 경우
2.  수가 k / 2 인 경우
3.  나머지 합이 k로 나누어 떨어지는 경우

1번의 경우에는 여러개의 수중에서  최대 1개만 부분집합에 포함이 가능하다 ( 2개 이상이 될 경우 합이 k로 나누어 떨어 지기 때문)

 

2번의 경우에도 여러개의 수중에서  최대 1개만 부분집합에 포함이 가능하다. ( 2개 이상이 될 경우 합이 k로 나누어 떨어지기 때문)

 

3번의 경우에는 나머지 합이 k 로 나누어 떨어지는 것 중 더 큰 값을 포함 시켜주면 최대를 구할 수 있다.

 

<전체코드>

public static int nonDivisibleSubset(int k, List<Integer> s) {
// Write your code here
    int[] remain = new int[k];
    
    for(int i = 0 ; i < s.size(); i++){
        remain[s.get(i) % k]++;
    }
    
    int answer = 0;
    
    if(k % 2 == 0){
        answer = Math.min(1, remain[k / 2]);
    }
    
    answer += Math.min(1, remain[0]);
    
    for(int i = 1 ; i < (k + 1) / 2 ; i++){
        if(i != k - i){
            answer += Math.max(remain[i], remain[k - i]);
        }
    }
    
    return answer;
}