문제 소개
두 개의 배열 nums1과 nums2가 있다고 가정해 보겠습니다. 배열에 담긴 값은 모두 1부터 6 사이(양 끝값 포함)입니다. 한 번의 연산으로 두 배열 중 어느 곳의 값이든 1~6 범위 안의 다른 값으로 변경할 수 있으며, 우리의 목표는 두 배열의 원소 합을 같게 만드는 데 필요한 최소 연산 횟수를 구하는 것입니다. 만약 어떻게 해도 두 합을 같게 만들 수 없다면 -1을 반환해야 합니다.
예를 들어 입력이 nums1 = [1,5,6], nums2 = [4,1,1]이라면 답은 2가 됩니다. 첫 번째 연산에서 nums2를 [4,1,1] → [4,1,6]으로 바꾸고, 두 번째 연산에서 [4,1,6] → [4,2,6]으로 바꾸면 합이 12로 nums1의 합과 같아지기 때문입니다.
알고리즘 접근 방식
이 문제는 그리디(Greedy) 전략으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 매 연산마다 두 합의 차이를 가장 많이 줄일 수 있는 선택을 하는 것입니다. 구체적인 단계는 다음과 같습니다.
nums1의 모든 원소의 합 s1과 nums2의 모든 원소의 합 s2를 계산합니다.
nums1과 nums2를 각각 오름차순으로 정렬합니다.
만약 s1 > s2라면 nums1과 nums2를 서로 교환하고, s1과 s2도 함께 교환합니다. (항상 s1 ≤ s2가 되도록 만듭니다.)
ans := 0 으로 초기화합니다.
left := 0, right := nums2의 길이 - 1 로 설정합니다.
left가 nums1의 길이보다 작거나 right가 0 이상인 동안 다음 과정을 반복합니다.
s1과 s2가 같다면 ans를 반환합니다.
curr_left := left가 nums1의 길이 미만이면 nums1[left], 아니면 7
curr_right := right가 0 이상이면 nums2[right], 아니면 0
만약 6 - curr_left ≥ curr_right - 1 이라면:
s1 := s1 + min(6 - curr_left, s2 - s1)
left := left + 1
그렇지 않다면:
s2 := s2 - min(curr_right - 1, s2 - s1)
right := right - 1
ans := ans + 1
반복이 끝난 후 s1과 s2가 같지 않으면 -1을, 같다면 ans를 반환합니다.
왜 이 방법이 최적일까요?
합이 작은 배열의 가장 작은 값을 올리면 한 번의 연산으로 최대 +5까지 늘릴 수 있고, 합이 큰 배열의 가장 큰 값을 내리면 최대 -5까지 줄일 수 있습니다. 즉, 매번 변화 폭이 가장 큰 원소를 조정하는 것이 합의 차이를 빠르게 줄이는 유일한 최선의 선택이므로, 이 그리디 방식이 최소 연산 횟수를 보장합니다. 여기서 포인터가 범위를 벗어났을 때 curr_left를 7로, curr_right를 0으로 설정하면 해당 선택지가 자동으로 탈락되어 코드가 깔끔하게 처리됩니다.
구현 예제
다음 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
def solve(nums1, nums2):
s1 = sum(nums1)
s2 = sum(nums2)
nums1.sort()
nums2.sort()
if s1 > s2:
nums1, nums2 = nums2, nums1
s1, s2 = s2, s1
ans = 0
left, right = 0, len(nums2) - 1
while left < len(nums1) or right >= 0:
if s1 == s2:
return ans
curr_left = nums1[left] if left < len(nums1) else 7
curr_right = nums2[right] if right >= 0 else 0
if 6 - curr_left >= curr_right - 1:
s1 += min(6 - curr_left, s2 - s1)
left += 1
else:
s2 -= min(curr_right - 1, s2 - s1)
right -= 1
ans += 1
return -1 if s1 != s2 else ans
nums1 = [1,5,6]
nums2 = [4,1,1]
print(solve(nums1, nums2))입력
[1,5,6], [4,1,1]
출력
2
정리
두 배열의 합 차이를 줄이기 위해 매번 변화 폭이 가장 큰 원소, 즉 합이 작은 쪽의 최솟값 또는 합이 큰 쪽의 최댓값을 조정하는 그리디 알고리즘을 적용하면 이 문제를 해결할 수 있습니다. 정렬에 O(n log n), 순회에 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. 반복 도중 두 합이 같아지는 순간 연산 횟수를 반환하고, 모든 조정 후에도 맞추지 못한다면 -1을 반환하면 됩니다.