Python에서 K-sum 쌍의 최대 수를 찾는 프로그램

<시간/>

nums라는 배열과 다른 값 k가 있다고 가정합니다. 한 번의 작업으로 합계가 k인 숫자에서 두 개의 요소를 선택하고 배열에서 제거할 수 있습니다. 어레이에서 수행할 수 있는 최대 작업 수를 찾아야 합니다.

따라서 입력이 nums =[8,3,6,1,5] k =9와 같으면 합이 9인 [3,6]을 삭제할 수 있으므로 출력은 2가 됩니다. 그런 다음 [8,1 ] 합도 9입니다.

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

counter :=숫자로 표시된 각 항목의 빈도를 보유하는 맵
res :=0
카운터의 각 숫자에 대해 다음을 수행합니다.
- 카운터[k-num]이 0이 아니면
  - num이 k - num과 같지 않으면
    - res :=res + counter[num] 및 counter[k-num]의 최소값
    - 카운터[k-num] :=0
    - 카운터[숫자] :=0
  - 그렇지 않으면
    - res :=res + (counter[num] / 2)의 몫
반환 결과

예시

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

from collections import Counter
def solve(nums, k):
   counter = Counter(nums)
   res = 0
   for num in counter:
      if counter.get(k-num, 0):
         if num != k - num:
            res += min(counter[num], counter[k-num])
            counter[k-num] = 0
            counter[num] = 0
         else:
            res += int(counter[num] / 2)

   return res

nums = [8,3,6,1,5]
k = 9
print(solve(nums, k))

입력

[8,3,6,1,5], 9