두 개의 리스트 nums와 multipliers가 있다고 가정해 보겠습니다. 우리가 수행할 수 있는 연산은 다음과 같습니다. nums에서 임의의 숫자 하나를 제거하고, multipliers에서도 임의의 숫자 하나를 제거한 뒤, 두 숫자를 곱합니다. 이 연산을 두 리스트 중 하나가 빌 때까지 반복하며, 곱해진 값들의 최대 합을 구하는 것이 목표입니다.
예를 들어 입력이 nums = [-4, 4, 3], multipliers = [-2, 2]라고 한다면 출력은 16이 됩니다. -4와 -2를 짝지어 곱하고, 4와 2를 짝지어 곱하면 (-4 × -2) + (4 × 2) = 16이 되기 때문입니다.
문제 해결 접근 방법
이 문제는 정렬과 그리디(Greedy) 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 음수끼리는 곱하면 양수가 된다는 점을 활용하는 것입니다.
- nums 리스트를 오름차순으로 정렬합니다.
- multipliers 리스트를 오름차순으로 정렬합니다.
- 결과값 res를 0으로 초기화합니다.
- 만약 nums의 길이가 multipliers보다 작다면, 두 리스트를 서로 교환합니다(더 긴 리스트를 nums로 사용).
- n := nums의 길이, m := multipliers의 길이로 설정합니다.
- i를 0부터 m-1까지 반복하면서:
- multipliers[i]가 0 이하인 경우 → 가장 작은 음수끼리 곱하는 것이 유리하므로, res에 nums[i] * multipliers[i]를 더합니다.
- 그렇지 않은 경우(양수인 경우) → 가장 큰 양수끼리 곱하는 것이 유리하므로, res에 multipliers[i] * nums[n - (m - i)]를 더합니다.
- 최종적으로 res를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.
def solve(nums, multipliers):
nums.sort()
multipliers.sort()
res = 0
if len(nums) < len(multipliers):
nums, multipliers = multipliers, nums
n, m = len(nums), len(multipliers)
for i in range(m):
if multipliers[i] <= 0:
res += nums[i] * multipliers[i]
else:
res += multipliers[i] * nums[n - (m - i)]
return res
nums = [-4, 4, 3]
multipliers = [-2, 2]
print(solve(nums, multipliers))입력
[-4, 4, 3], [-2, 2]
출력
16
동작 원리 설명
위 코드에서 정렬 후 nums는 [-4, 3, 4], multipliers는 [-2, 2]가 됩니다. 첫 번째 반복에서 multipliers[0] = -2는 0 이하이므로 nums[0] = -4와 곱하여 8을 얻습니다. 두 번째 반복에서 multipliers[1] = 2는 양수이므로 nums[n - (m - i)] = nums[3 - 1] = nums[2] = 4와 곱하여 8을 더합니다. 따라서 최종 결과는 8 + 8 = 16이 됩니다.
이 알고리즘의 시간 복잡도는 정렬이 지배적이므로 O(n log n)입니다. 음수는 음수와, 양수는 양수와 매칭하는 그리디 전략 덕분에 각 단계에서 최적의 선택을 보장할 수 있습니다.