문제 개요
2n개의 정수로 이루어진 배열이 주어졌을 때, 이 숫자들을 (a1, b1), (a2, b2), ..., (an, bn) 형태로 n개의 쌍(pair)으로 묶어야 합니다. 목표는 모든 쌍에 대해 min(ai, bi)의 합, 즉 각 쌍에서 작은 값들의 총합이 최대가 되도록 만드는 것입니다.
예를 들어 입력이 [1, 4, 3, 2]라고 가정해 보겠습니다. 이 경우 n은 2이며, 최대 합은 4가 됩니다. (1, 2)와 (3, 4)로 묶으면 min(1, 2) + min(3, 4) = 1 + 3 = 4가 되기 때문입니다.
해결 접근 방법
이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- n을 배열의 크기라고 정의합니다.
- 배열을 오름차순으로 정렬합니다.
- answer 변수를 0으로 초기화합니다.
- i를 0부터 n까지 2씩 증가시키면서 반복합니다.
- answer에 array[i] 값을 누적하여 더합니다.
- answer를 반환합니다.
배열을 정렬하면 작은 수들이 앞쪽에 몰리게 되므로, 인접한 두 수를 하나의 쌍으로 묶는 것이 가장 유리합니다. 이렇게 하면 각 쌍에서 버려지는 큰 값의 손실을 최소화할 수 있고, 결과적으로 최솟값들의 합이 최대가 됩니다.
구현 예제
아래 파이썬 구현을 통해 더 잘 이해해 보겠습니다.
class Solution(object):
def arrayPairSum(self, a):
"""
:type nums: List[int]
:rtype: int
"""
n = len(a)
a.sort()
ans = 0
for i in range(0, n, 2):
ans += a[i]
return ans
ob1 = Solution()
print(ob1.arrayPairSum([1,4,3,2]))
입력
[1,4,3,2]
출력
4
복잡도 분석
정렬에 O(n log n)의 시간이 소요되므로 전체 시간 복잡도는 O(n log n)이며, 별도의 추가 공간 없이 제자리 정렬을 사용하면 공간 복잡도는 O(1)입니다.