숫자 배열과 정수 k가 주어졌을 때, 이 배열을 모든 쌍의 합이 k로 나누어 떨어지도록 쌍(pair)으로 분할할 수 있는지 확인해야 합니다.
예를 들어 입력이 arr = [5, 15, 6, 9], k = 7이라면 결과는 True입니다. (5, 9)와 (15, 6)으로 쌍을 지으면 각각의 합이 14와 21로 모두 7로 나누어 떨어지기 때문입니다.
접근 방법: 나머지 활용하기
핵심 아이디어는 나머지(remainder)입니다. 두 수의 합이 k로 나누어 떨어지려면, 두 수를 k로 나눈 나머지의 합이 0 또는 k가 되어야 합니다. 이를 정리하면 다음과 같습니다.
- 나머지가 0인 수는 나머지가 0인 수끼리만 짝을 이룰 수 있으며, 그 개수는 반드시 짝수여야 합니다.
- 나머지가 r인 수는 나머지가 k − r인 수와 짝을 이루어야 하므로, 두 그룹의 개수가 정확히 일치해야 합니다.
- 나머지가 k/2인 수(2 × r == k)는 같은 나머지를 가진 수끼리 짝을 이루므로, 역시 개수가 짝수여야 합니다.
또한 배열의 길이가 홀수라면 애초에 쌍으로 나누는 것이 불가능하므로 즉시 False를 반환합니다.
알고리즘 단계
- n := 배열의 크기
- n이 홀수이면 False를 반환합니다.
- occurrences := 기본값이 0인 빈 딕셔너리(defaultdict)를 준비합니다.
- 배열의 모든 요소에 대해 ((array[i] mod k) + k) mod k를 키로 삼아 occurrences의 개수를 1씩 증가시킵니다. (음수도 올바르게 처리하기 위해 k를 더한 뒤 다시 mod 연산을 적용합니다.)
- 배열을 다시 순회하며 각 요소의 나머지에 대해 다음을 검사합니다.
- 2 × remainder == k인 경우: occurrences[remainder]가 홀수이면 False를 반환합니다.
- remainder == 0인 경우: occurrences[remainder]가 홀수이면(& 1이 0이 아니면) False를 반환합니다.
- 그 외의 경우: occurrences[remainder]와 occurrences[k − remainder]가 다르면 False를 반환합니다.
- 모든 검사를 통과하면 True를 반환합니다.
구현 예제
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
복잡도 분석
배열을 두 번 순회하므로 시간 복잡도는 O(n)입니다. 나머지 값의 종류는 최대 k개이므로 공간 복잡도는 O(min(n, k))입니다.