[HackerRank] Non-Divisible Subset

⭐ 나의 풀이

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'nonDivisibleSubset' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER k
#  2. INTEGER_ARRAY s
#
        
def nonDivisibleSubset(k, s) :
    # Write your code here
    count_mod = [0] * k
    for value in s :
        count_mod[value % k] += 1
    answer = min(1, count_mod[0])
    if k % 2 == 0 : answer += min(1, count_mod[k//2])
    for i in range(1, k//2+1) :
        if i != k-i :
            answer += max(count_mod[i], count_mod[k-i])
    return answer
        
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    k = int(first_multiple_input[1])

    s = list(map(int, input().rstrip().split()))

    result = nonDivisibleSubset(k, s)

    fptr.write(str(result) + '\n')

    fptr.close()

어떠한 두 숫자 합도 k로 나눌 수 없는 최대 부분 집합 S'의 길이를 구한다.

0~k-1까지 나머지별로 개수를 센다.

k가 짝수면, 나머지 a==b가 있다. a + b = k가 되어서 조건을 충족하지 못한다. 부분집합에 최대 1번만 들어가야 함.

나머지 0일 때도 최대 1번만 들어가야 한다. 

 

 

# 시간초과
#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'nonDivisibleSubset' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER k
#  2. INTEGER_ARRAY s
#
combinations_result = []
flag = True     # not evenly divisible by k

def make_combinations(n, idx, sub_s, size, s) :
    global combinations_result
    if size == 0 : 
        combinations_result.append(sub_s[:])
        return
    for i in range(idx, n) :
        sub_s.append(s[i])
        make_combinations(n, i+1, sub_s, size - 1, s)
        sub_s.pop()

def check(sub_s, depth, tmp, start, k) :
    global flag
    if depth == 0 :
        if sum(tmp) % k == 0:
            flag = False
        return
    for i in range(start, len(sub_s)) :
        tmp.append(sub_s[i])
        check(sub_s, depth - 1, tmp, i+1, k)
        tmp.pop()
        
def nonDivisibleSubset(k, s) :
    # Write your code here
    global combinations_result, flag
    len_s = len(s)
    for size in range(len_s, 1, -1) :
        combinations_result = []
        make_combinations(len_s, 0, [], size, s)
        for combi in combinations_result :
            check(combi, 2, [], 0, k)
            if flag :
                return size
            flag = True
    return 
        
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    k = int(first_multiple_input[1])

    s = list(map(int, input().rstrip().split()))

    result = nonDivisibleSubset(k, s)

    fptr.write(str(result) + '\n')

    fptr.close()

조합을 만들었다.

너무 복잡하게 구현했군..

 

 

💡 다른 사람 풀이

# https://medium.com/@mrunankmistry52/non-divisible-subset-problem-comprehensive-explanation-c878a752f057
def nonDivisibleSubset(k, s) :
    count = [0] * k

    for i in s :
        remainder = i % k
        count[remainder] += 1

    ans = min(count[0], 1)      # Handling case 1

    if k % 2 == 0 :             # Handling case even exception case
        ans += min(count[k//2], 1)

    for i in range(1, k//2+1) :     # Check for the pairs and take appropriate count
        if i != k - i :             # Avoid over-counting when k is even
            ans += max(count[i], count[k-i])
    return ans

k로 어떤 수를 나누면 나머지는 0 ~ k-1까지 나온다.

배열 s의 원소들을 k로 나눠보면서 count 배열에 나머지의 개수를 넣는다.

아래와 같은 경우는 p + q를 k로 나눌 수 있어서 제외시킨다.

1. 나머지 p, q가 0일 때
2. 나머지 p + q = k일 때

주의할 점은 k가 짝수면 p==q니까 건너띈다.

 

 

 

 

---

문제 출처 👇👇

https://www.hackerrank.com/challenges/non-divisible-subset/problem?isFullScreen=true 

 

 

참고👇👇

https://insanelysimple.tistory.com/195

hackerrank Non-Divisible Subset 풀이