[HackerRank] Non-Divisible Subset

[문제 링크]

[입력]

int S[n]: 정수형 배열 , 길이는 n 이다.
int k: 나누는 숫자.

[출력]

int: 기준을 만족하는 S 의 부분집합중 가장 원소의 갯수가 많은 부분집합의 길이

[기준]

부분집합의 어떤 두 원소를 더해도 k 로 나누어 떨어지지 않아야 한다.

[코드]

def nonDivisibleSubset(k, s):
    # Write your code here
    reminder = [0]*k
    result = 0
    for item in s:
        reminder[item%k]+=1
        
    result = min(reminder[0],1)
    
    for idx in range(1,k//2+1):
        if(idx != k-idx):
            result += max(reminder[idx] , reminder[k-idx])
    if k%2==0:
        result+=1
    return result

좋은 웹페이지 즐겨찾기