문제 설명
숫자로 이루어진 리스트 nums와 목표값 target이 주어졌을 때, 만들 수 있는 쌍(pair)의 최대 개수를 구하는 것이 목표입니다. 여기서 각 쌍은 인덱스 i < j를 가져야 하고, 한 인덱스는 서로 다른 쌍에 중복 사용될 수 없으며, 두 값의 절대 차이는 조건 |nums[i] - nums[j]| >= target을 만족해야 합니다.
예를 들어 nums = [2, 4, 6, 10, 11], target = 5가 입력으로 주어지면 출력은 2가 됩니다. (2, 10)과 (4, 11)이라는 두 쌍을 만들 수 있으며, 각각 차이가 8과 7로 목표값 5 이상이기 때문입니다.
접근 방법
이 문제는 정렬과 투 포인터(two pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 리스트 A의 크기를 N에 저장합니다.
- 리스트 A를 오름차순으로 정렬합니다.
- 정답을 저장할 변수 ans를 0으로 초기화합니다.
- 두 번째 포인터 j를 N / 2로 설정합니다.
- i를 0부터 N / 2까지 반복하면서 다음을 수행합니다.
- j가 N 미만이고 A[j] - A[i]가 target보다 작은 동안 j를 1씩 증가시킵니다.
- j가 N 미만이면 ans를 1 증가시키고, j도 1 증가시킵니다.
- 반복이 끝나면 ans를 반환합니다.
핵심 아이디어는 정렬된 리스트를 반으로 나누어 앞부분의 작은 값과 뒷부분의 큰 값을 매칭하는 것입니다. 앞쪽 원소 하나당 뒤쪽에서 조건을 만족하는 원소 하나를 탐욕적(greedy)으로 연결하므로, 가능한 최대 매칭 개수를 보장할 수 있습니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, A, target):
N = len(A)
A.sort()
ans = 0
j = N >> 1
for i in range(N >> 1):
while j < N and A[j] - A[i] < target:
j += 1
if j < N:
ans += 1
j += 1
return ans
ob = Solution()
nums = [2, 4, 6, 10, 11]
target = 5
print(ob.solve(nums, target))
입력
[2, 4, 6, 10, 11], 5
출력
2
복잡도 분석
정렬에 O(N log N)의 시간이 소요되고, 이후 투 포인터 탐색은 O(N)이므로 전체 시간 복잡도는 O(N log N)입니다. 추가 공간은 정렬 방식에 따라 다르지만 일반적으로 O(1) 수준으로 매우 효율적입니다.