Non-Divisible Subset

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

문제

숫자가 담긴 배열 S가 주어질 때, 요소 2개를 골라 합한 값이 k로 나누어 지지 않는 요소들로만 구성된 부분집합 S' 중 가장 긴 집합의 길이를 출력하라. S=[19, 10, 12, 10, 24, 25, 22] 이고 k=4 일 때, S'[0]=[10, 12, 25], S'[1]=[19, 22, 24]가 최대 길이의 부분집합이다.

풀이

일단 문제 이해하는 데에만 오랜시간이 걸렸다. 문제에서 S’[0] 안에 있는 요소들 중 어떤 두개의 요소를 골라서 합해도 4로 나누어 지지 않는다. S’[1]도 마찬가지이다. 다시 말하면 S에 있는 숫자로 집합을 만들라는 얘기다. 하지만 무식하게 조합을 사용하여 모든 경우의 수를 만드려하다 보면 시간초과가 날 것이라는 것을 짐작할 수 있다. 모든 알고리즘 문제는 규칙을 찾는 것이 중요하다.

두 개의 숫자를 더한 값이 4로 나누어 지지 않으려면 각각의 수를 4로 나눈 나머지를 더했을 때 4나 0이 되면 안된다. 예를들어 19와 22를 각각 4로 나눈 나머지는 3, 2이고 이는 4나 0이 아니므로 더한 값도 4로 나누어 떨어지지 않는다. 조금더 편하게 생각하기 위해 반대로 생각해보면 나머지의 합이 4가 되는 값 중 항상 하나만 선택하면 된다. 즉, 나머지가 1인 값이 들어가는 집합은 나머지가 3인 값이랑 함께 있으면 절대 안된다.

loop를 돌리면서 두 값 중 선택하면 된다. 더했을 때 4가 되는 경우의 수는 (1, 3), (2, 2) 이고, 1과 3 중 많은 요소를 더하고 2와 2는 함께 붙어있을 수 없으므로 무조건 한개만 추가할 수 있다. 또한 나머지가 0인 요소가 있다면 같은 이유로 한개만 추가할 수 있다.

def nonDivisibleSubset(k, s):
    # 주어진 집합에서 어떤 두개의 수를 골라 더했을 때 k로 나누어 떨어지지 않는 부분집합을 구하라
    new_s = [ss%k for ss in s]
    
    result = 0
    # 좌우로 중복되지 않은 곳까지만 검사 (k가 4이면 2까지, k가 5이면 2까지)
    # (1, k-1), (2, k-2), ...
    for i in range(1, k//2+1):
        # k가 4일 때, (2,2)와 같은 상황일 때, 2가 존재한다면 한번만 추가할 수 있다.
        if i == k-i and i in new_s: result += 1
        else:
            # 나머지의 합이 k가 되는 값 둘 중에 하나만 선택
            result += max(new_s.count(k-i), new_s.count(i))
    
    # 나머지가 0인 값이 있는 경우는 딱 하나만 선택할 수 있다.
    if 0 in new_s: result += 1

    return result

문제의 핵심은 특정 조건일 때, 선택할 수 있는 경우의 수가 명확하게 제한적이라는 것이다. 또한 정확한 경우의 수를 구하는 것이 아닌 최대를 구하는 것이므로 유연하게 풀 수 있다.