숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, 이 리스트를 서로 다른 두 요소끼리 짝지은 쌍(pair)들로 분할하되, 각 쌍의 합이 k로 나누어 떨어지도록 할 수 있는지 확인하는 문제입니다.
예를 들어, 입력이 nums = [4, 7, 2, 5], k = 6이라면 결과는 True가 됩니다. 리스트를 (4, 2)와 (7, 5)로 분할하면 각 쌍의 합은 6과 12로, 모두 6으로 나누어 떨어지기 때문입니다.
문제 해결 접근 방식
이 문제는 나머지(remainder)의 성질을 이용하면 효율적으로 해결할 수 있습니다. 두 수의 합이 k로 나누어 떨어지려면, 두 수를 k로 나눈 나머지의 합이 0 또는 k가 되어야 합니다. 즉, 나머지가 i인 수와 나머지가 k-i인 수가 서로 짝을 이루어야 하며, 나머지가 0인 수들은 서로 짝을 이루어야 합니다.
구체적인 풀이 단계는 다음과 같습니다:
- nums의 요소 개수가 홀수라면 쌍으로 나눌 수 없으므로 False를 반환합니다.
- 크기가 k인 카운트 배열(count)을 만들고 0으로 초기화한 후, 각 숫자를 k로 나눈 나머지 값에 해당하는 인덱스의 개수를 1씩 증가시킵니다.
- 나머지가 0인 숫자들의 개수(count[0])가 홀수라면 이들을 서로 짝지을 수 없으므로 False를 반환합니다.
- i를 1부터 k // 2까지 반복하면서, 나머지가 i인 숫자의 개수(count[i])와 나머지가 k-i인 숫자의 개수(count[k-i])가 일치하지 않으면 False를 반환합니다.
- 모든 조건을 통과하면 True를 반환합니다.
참고로 k가 짝수인 경우, 나머지가 k/2인 숫자들은 서로 짝을 이루어야 하므로 그 개수 역시 짝수여야 합니다. 위 반복문에서 i == k - i가 되는 지점이 바로 이 경우에 해당합니다.
구현 예시
class Solution:
def solve(self, nums, k):
if len(nums) % 2:
return False
count = [0] * k
for n in nums:
count[n % k] += 1
if count[0] % 2:
return False
for i in range(1, k // 2 + 1):
if count[i] != count[k - i]:
return False
return True
ob = Solution()
nums = [4, 7, 2, 5]
k = 6
print(ob.solve(nums, k))
입력
[4, 7, 2, 5], 6
출력
True
복잡도 분석
이 알고리즘은 리스트를 한 번만 순회하여 나머지를 계산하고(O(n)), 이후 최대 k/2번의 비교를 수행하므로 전체 시간 복잡도는 O(n + k), 공간 복잡도는 크기가 k인 배열 하나만 사용하므로 O(k)입니다. 이는 가능한 모든 쌍을 검사하는 브루트 포스 방식(O(n²))보다 훨씬 효율적입니다.