num이라는 배열이 있고 이 배열에 짝수개의 요소가 포함되어 있고 다른 값 k가 있다고 가정합니다. 각 쌍의 합이 k로 나누어지도록 num을 정확히 n/2 쌍으로 분할해야 합니다. 그렇게 할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
따라서 입력이 nums =[9,5,3,4,7,10,20,8] k =3과 같으면 (9,3), (5)와 같은 쌍을 만들 수 있기 때문에 출력은 True가 됩니다. ,7), (4,20), (8,10), 모든 쌍의 합은 3으로 나눌 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
dp :=새 목록
-
개수:=0
-
숫자의 각 x에 대해 수행
-
t:=k - (x 모드 k)
-
t가 k와 같으면
-
개수 :=개수 + 1
-
-
그렇지 않으면
-
dp의 끝에 t 삽입
-
-
-
카운트 모드 2가 0과 같지 않으면
-
거짓을 반환
-
-
목록 정렬 dp
-
낮음 :=0
-
높음 :=dp 크기 - 1
-
낮은 동안 <높은, 수행
-
dp[low] + dp[high]가 k와 같지 않으면
-
거짓을 반환
-
-
낮음 :=낮음 + 1
-
높음 :=높음 - 1
-
-
참을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
def solve(nums, k): dp=[] count=0 for x in nums: t=k-(x % k) if t == k: count+=1 else: dp.append(t) if count % 2 != 0: return False dp.sort() low = 0 high = len(dp)-1 while low < high: if dp[low] + dp[high] != k: return False low += 1 high -= 1 return True nums = [9,5,3,4,7,10,20,8] k = 3 print(solve(nums, k))
입력
[9,5,3,4,7,10,20,8], 3
출력
True