Python에서 동일한 합계로 k 하위 배열로 분할할 수 있는지 확인

nums라는 숫자 배열이 있고 또 다른 값 K가 있다고 가정합니다. 각 하위 배열의 요소 합이 동일하도록 배열 num을 K개의 연속 하위 배열로 분할할 수 있는지 확인해야 합니다.

따라서 입력이 nums =[2, 5, 3, 4, 7] k =3과 같으면 [(2, 5), (3, 4), (7)] 모두 합이 7입니다.

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

• n :=숫자 크기
• cumul_sum :=nums의 모든 요소의 누적 합계
• total_sum :=cumul_sum[n - 1]
• total_sum이 k로 나누어지지 않으면
  • 거짓을 반환
• 카운트:=0, 위치:=-1
• 0 ~ n - 1 범위의 i에 대해
  • pos가 -1과 같으면
    • 하위 :=0
  • 그렇지 않으면
    • sub :=cumul_sum[pos]
  • cumul_sum[i] - sub가 (total_sum / K)와 같으면
    • pos :=나
    • 카운트 :=카운트 + 1
  • 그렇지 않으면 cumul_sum[i] - cumul_sum[pos]> (total_sum / K)일 때
    • 루프에서 나오다
• 카운트가 K와 같으면 true를 반환하고 그렇지 않으면 false를 반환

예시

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

def solve(nums, k):
   n = len(nums)
   cumul_sum = [0 for i in range(n)]
   cumul_sum[0] = nums[0]
   for i in range(1, n):
      cumul_sum[i] = cumul_sum[i - 1] + nums[i]
   total_sum = cumul_sum[n - 1]
   if total_sum % k != 0:
      return False
   count = 0
   pos = -1
   for i in range(n):
      if pos == -1:
         sub = 0
      else:
         sub = cumul_sum[pos]
      if cumul_sum[i] - sub == total_sum / k:
         pos = i
         count += 1
      elif cumul_sum[i] - cumul_sum[pos] > total_sum / k:
         break
   return count == k
nums = [2, 5, 3, 4, 7]
k = 3
print(solve(nums, k))

입력

[2, 5, 3, 4, 7], 3

출력

True