Non-Divisible Subset

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

 

이거 실패하고 선배들의 풀이를 봤는데도 이해가 안되어서 3일 끙끙되었는데 예제를 직접 풀어보며 관계를 파악해보니 금방 되었다.... 역시 내 두뇌와 손을 사용해야 한다...

 

import collections


def foo(nums, k):
    '''
    이것은 나머지의 관계를 파악하는 문제이다.

    문제에서 k는 나누는수로 주어진다. nums의 숫자들은 k로 나누어 나머지가 같은 것끼리
    집합을 만들 수 있다. 이들 중 두 집합을 p, q라고 하자. 집합을 구성한 나머지들은
     어떤 관계를 갖고 있다. 각각의 집합을 만들게 한 나머지를 P, Q라 하자. 이들은
     P + Q = k라는 관계를 가진다. 이것이 의미하는 것은 무엇일까? 그것은 p, q가
     배타적인 관계를 갖고 있다는 것이다. 예를 들어 nums=[1,2,3,4,5]이고
    k=3이라 하자. 이들을 k로 나누어 나머지로 키를 삼고 개수를 센다. 이러면

    0: 1개 = 3
    1: 2개 = 1, 4
    2: 2개 = 2, 5

    P + Q = k가 되는 값은 각각 1, 2이다.  p = {1, 4}, q = {2, 5}이다.
    허나 {1, 4}는 {2, 5} 중 어느 것 하나도 서로 더하면 3으로 나누어 떨어진다.
    따라서 p, q중 개수가 더 많은 걸 k로 떨어지지 않는 부분 집합으로 삼을 수 있다.
    집합을 이루는 원소들은 떨어지지 않는 수들의 배수이기 때문에 더해도 마찬가지가 된다.

    p=q=0인 경우는 특별하다. 이 경우 숫자는 최대 1개만 쓸 수 있다. p={3,6,9}이 있다고 하면
    어떻게 숫자를 조합해도 3으로 떨어진다. 모두 0으로 떨어지기 때문이다.

    마지막으로 특별한 경우는 k=짝수인 경우이다. 짝수인 경우 k/2가 나머지로 나올 수 있는데,
    k/2 + k/2 = k이다. k=4일 때 {2, 6}을 생각해보자. 따라서 이것도 최대 1개만 쓸 수 있다.
    '''
    vals = collections.defaultdict(int)
    for n in nums:
        vals[n % k] += 1

    size = min(vals[0], 1)

    if k % 2 == 0:
        size += min(vals[k // 2], 1)
        vals[k // 2] = 0

    for i in range(1, k // 2 + 1):
        size += max(vals[i], vals[k - i])

    return size