문제 설명
nums라는 배열이 있고, 이 배열에는 짝수 개의 요소가 들어 있으며, 또 다른 값 k가 주어진다고 가정해 보겠습니다. 우리는 nums를 정확히 n/2개의 쌍으로 나누어 각 쌍의 합이 k로 나누어떨어지도록 만들어야 합니다. 가능하다면 true를, 그렇지 않다면 false를 반환합니다.
예를 들어, 입력이 nums = [9,5,3,4,7,10,20,8], k = 3이라면 출력은 True입니다. (9,3), (5,7), (4,20), (8,10)과 같은 쌍을 만들 수 있고, 각 쌍의 합인 12, 12, 24, 18이 모두 3으로 나누어떨어지기 때문입니다.
접근 방법
이 문제의 핵심은 각 숫자를 k로 나눈 나머지에 착안하는 것입니다. 두 수의 합이 k로 나누어떨어지려면 두 수의 나머지 합이 0 또는 k가 되어야 하므로, 나머지가 r인 수는 반드시 나머지가 k-r인 수와 짝을 이루어야 합니다.
이 원리를 바탕으로 한 해결 단계는 다음과 같습니다.
- 빈 리스트 dp와 카운터 count를 초기화합니다.
- nums의 각 요소 x에 대해 t = k - (x mod k)를 계산합니다.
- t가 k와 같다면(x가 k로 나누어떨어진다면) count를 1 증가시키고, 그렇지 않으면 t를 dp에 추가합니다.
- k로 나누어떨어지는 수들은 서로 짝을 이루어야 하므로, count가 홀수라면 False를 반환합니다.
- dp를 오름차순으로 정렬한 뒤 투 포인터(low, high)를 사용해 양쪽 끝부터 검사합니다.
- dp[low] + dp[high]가 k가 아니면 False를 반환하고, 모든 쌍이 조건을 만족하면 True를 반환합니다.
예제 코드
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
복잡도 분석
시간 복잡도는 정렬 과정 때문에 O(n log n)이며, 추가 리스트 dp를 사용하므로 공간 복잡도는 O(n)입니다. 나머지 값을 미리 계산해 두고 투 포인터로 짝을 검증하기 때문에 전체 로직이 직관적이면서도 효율적으로 동작합니다.