숫자 배열이 있고 또 다른 숫자 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이 아니면
- 거짓을 반환
- 회수[나머지] 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