파이썬에서 합이 k로 나눌 수 있는 쌍으로 배열을 나눌 수 있는지 확인

숫자 배열이 있고 또 다른 숫자 k가 있다고 가정하면 주어진 배열이 모든 쌍의 합이 k로 나눌 수 있도록 쌍으로 나눌 수 있는지 확인해야 합니다.

따라서 입력이 arr =[5, 15, 6, 9] k =7과 같으면 (5, 9) 및 (15, 6)과 같은 쌍을 취할 수 있으므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=배열의 크기
• n이 홀수이면
  • 거짓을 반환
• occurrences :=빈 사전, 일부 키가 없으면 누락된 키의 값으로 0을 반환
• 0에서 n 사이의 i에 대해
  • 발생 횟수[((array[i] mod k) + k) mod k]를 1 증가
• 0에서 n 사이의 i에 대해
  • 나머지 :=((array[i] mod k) + k) mod k
  • 2 * 나머지가 k와 같으면
    • 발생 횟수[나머지]가 홀수이면
      • 거짓을 반환
  • 그렇지 않고 나머지가 0일 때
    • 회수[나머지] AND 1이 0이 아니면
      • 거짓을 반환
  • 그렇지 않으면 발생[remainder]이 발생[k - 나머지]와 같지 않으면
    • 거짓을 반환
• 참 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

from collections import defaultdict
def solve(array, k):
   n = len(array)
   if n % 2 != 0:
      return False
   occurrences = defaultdict(lambda : 0)
   for i in range(0, n):
      occurrences[((array[i] % k) + k) % k] += 1
   for i in range(0, n):
      remainder = ((array[i] % k) + k) % k
      if (2 * remainder == k):
         if (occurrences[remainder] % 2 != 0):
            return False
      elif (remainder == 0):
         if (occurrences[remainder] & 1):
            return False
         elif (occurrences[remainder] != occurrences[k - remainder]):
            return False
   return True
arr = [5, 15, 6, 9]
k = 7
print(solve(arr, k))

입력

[5, 15, 6, 9], 7

출력

True