문제 링크

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

주의 사항

모든 subset의 경우의 수를 다 구할 경우, n이 최대 10의 5승까지 가능하므로 시간복잡도에서 문제 발생

• k로 나눈 나머지를 활용하여 문제 풀기

두 수의 합이 k로 나누어 떨어지지 않으려면 각 숫자의 나머지의 합이 0과 k만 아니면 된다.

문제 풀이

def nonDivisibleSubset(k, s):
    remain_dict = defaultdict(int)
    for i in s:
        remain_dict[i%k] += 1 
        # 각 나머지 별로 몇개의 숫자를 가지고 있는지 확인

    check = [] # 확인한 나머지 check하기 위한 변수
    answer = 0
    
    for remain in remain_dict:
        opposite_remain = k-remain
        # 현재 나머지의 짝꿍 나머지 opposite_remain 구하기
        # 둘이 더해서 k가 된다면 나누어 두 수의 합이 나누어 떨어짐
        # 두 나머지를 가진 수들끼리는 한 subset에 있을 수 없음
        
        if remain in check: 
            continue
            # 이미 확인한 나머지라면 넘기기
            
        if remain == 0:
            answer += 1 
            # k로 나누어 떨어지는 수가 있다면 1개만 허용 가능 
            # (남은 수들의 나머지가 절대로 k가 될 수 없기에 0을 더해도 괜찮음)
            
        elif remain == opposite_remain and opposite_remain in remain_dict:
            answer += 1
            # k가 짝수일 경우, remain과 opposite_remain이 같을 수 있음
            # 이때에는 해당 나머지를 갖는 숫자 중 단 하나만 subset에 포함 가능
            
        elif opposite_remain in remain_dict:
            answer += max(remain_dict[remain], remain_dict[opposite_remain])
            # 나머지와 짝꿍 나머지 모두 remain_dict에 있다면
            # 그 중 수가 많은 쪽을 subset에 더하기
        else:
            answer += remain_dict[remain]
        
        check.append(remain)
        check.append(opposite_remain)
    return answer