알고리즘 문제를 풀다 보면 배열 사이의 '차이'를 최소화해야 하는 상황을 자주 만나게 됩니다. 이번 글에서는 절대 합 차이(Absolute Sum Difference) 개념과, nums1 배열의 원소를 최대 한 번만 교체할 수 있을 때 이 값을 최소화하는 파이썬 풀이법을 알아보겠습니다.
문제 정의
같은 크기를 가진 두 개의 양수 배열 nums1과 nums2가 주어집니다. 이때 두 배열의 절대 합 차이는 다음과 같이 정의됩니다.
|nums1[i] - nums2[i]| 의 합 (0 <= i < n, 0-인덱스 기준)
여기서 우리는 nums1의 원소 중 최대 하나를 골라, nums1에 이미 존재하는 다른 값으로 교체할 수 있습니다. 목표는 이 교체를 활용해 절대 합 차이를 최소화하는 것이며, 결과값이 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예시로 이해하기
입력이 nums1 = [2, 8, 6], nums2 = [3, 4, 6]이라고 가정해 봅시다. 이 경우 정답은 3이며, 최적 해는 두 가지가 존재합니다.
- 인덱스 1의 원소(8)를 인덱스 0의 원소(2)로 교체: [2, 8, 6] → [2, 2, 6]
- 인덱스 1의 원소(8)를 인덱스 2의 원소(6)로 교체: [2, 8, 6] → [2, 6, 6]
두 경우 모두 합 차이는 |2-3| + (|2-4| 또는 |6-4|) + |6-6| = 3으로 동일합니다.
풀이 전략
이 문제는 직관적인 탐욕(Greedy) 접근으로 해결할 수 있습니다. 핵심 아이디어는 차이가 가장 큰 위치를 찾아, 그 자리를 nums1의 다른 원소로 대체했을 때 차이가 가장 작아지는 값을 선택하는 것입니다.
단계별 알고리즘
- nums1과 nums2가 완전히 같다면 차이가 0이므로 즉시 0을 반환합니다.
- |nums1[i] - nums2[i]|가 가장 큰 인덱스 ind를 찾습니다. 이 위치가 교체 후보입니다.
- ind를 제외한 나머지 원소들 중에서 |nums1[i] - nums2[ind]|가 가장 작은 값을 만드는 인덱스 index를 찾습니다.
- ind 위치의 값을 nums1[index]로 바꾼 것으로 간주하고 전체 합을 다시 계산합니다.
- 결과를 10^9 + 7로 나눈 나머지를 반환합니다.
파이썬 구현 코드
def solve(nums1, nums2):
if(nums1 == nums2):
return(0)
minn_diff = float('-inf')
ind = -1
for i in range(len(nums1)):
if(abs(nums1[i]-nums2[i]) > minn_diff):
ind = i
minn_diff = abs(nums1[i]-nums2[i])
diff = abs(nums1[ind]-nums2[ind])
index = ind
for i in range(len(nums1)):
if(i != ind):
if(abs(nums1[i]-nums2[ind]) < diff):
index = i
diff = abs(nums1[i]-nums2[ind])
summ = 0
for i in range(len(nums1)):
if(i == ind):
summ += abs(nums1[index]-nums2[i])
else:
summ += abs(nums1[i]-nums2[i])
return(summ % (10**9 + 7))
nums1 = [2, 8, 6]
nums2 = [3, 4, 6]
print(solve(nums1, nums2))입력
[2,8,6], [3,4,6]
출력
3
복잡도 분석 및 마무리
위 코드는 세 번의 선형 순회를 수행하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 참고로 더 큰 입력에서 성능을 높이려면 두 번째 단계에서 이진 탐색(binary search)을 활용해 nums2[ind]에 가장 가까운 값을 O(log n)에 찾는 방법도 있습니다.
이처럼 '차이가 가장 큰 지점을 우선 공략한다'는 탐욕적 사고는 배열 최적화 유형의 문제에서 매우 유용하게 쓰이는 패턴이니, 코딩 테스트 준비하실 때 꼭 기억해 두시길 바랍니다.