[LeetCode 75] Medium - 1679. Max Number of K-Sum Pairs ☆

1679. Max Number of K-Sum Pairs

 

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

 

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

 

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9

Hint 1

 

The abstract problem asks to count the number of disjoint pairs with a given sum k.

 

Hint 2

 

For each possible value x, it can be paired up with k - x.

 

Hint 3

 

The number of such pairs equals to min(count(x), count(k-x)), unless that x = k / 2, where the number of such pairs will be floor(count(x) / 2).

 

 

문제 설명

이 문제는 두 숫자의 합이 k가 되는 최대 쌍(pair)을 찾는 문제입니다. 배열 nums에서 각 숫자는 한 번만 사용할 수 있습니다.
주어진 제약에 따라, 합이 k가 되는 두 숫자를 찾아 제거하는 작업을 가능한 한 많이 수행해야 합니다.

---

조건

1. 입력:
   • nums: 정수 배열 (1 ≤ nums.length ≤ 10^5).
   • k: 목표 합 (1 ≤ k ≤ 10^9).
2. 출력:
   • 최대 쌍의 개수를 반환합니다.
3. 제약:
   • nums[i] 는 한 번 사용되면 다시 사용할 수 없습니다.
   • 1 ≤ nums[i] ≤ 10^9.

---

문제 접근

이 문제는 쌍(pair) 찾기 문제로 다음과 같은 방법으로 해결할 수 있습니다.

아이디어 1: 브루트 포스

1. 모든 가능한 두 숫자 쌍을 확인하여 합이 k인지 확인.
2. k가 되는 쌍을 찾으면 배열에서 두 숫자를 제거하고 작업을 반복.
3. 문제점:
   • 시간 복잡도 O(n^2)로, 입력 크기가 클 때 비효율적.

아이디어 2: 해시맵 활용

1. 각 숫자에 대해:
   • 해당 숫자를 사용하여 k−현재 숫자를 찾습니다.
   • 이미 해시맵에 k−현재 숫자 가 존재하면 쌍을 형성할 수 있음.
2. 장점:
   • 시간 복잡도 O(n), 공간 복잡도 O(n) 로 효율적.
   • 각 숫자의 빈도를 빠르게 추적할 수 있음.

from collections import Counter

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        # Step 1: 숫자 빈도수를 저장하는 Counter 생성
        freq = Counter(nums)  # nums 배열의 각 숫자와 그 빈도수를 저장
        # 예제: nums = [3, 1, 3, 4, 3], k = 6
        # freq = {3: 3, 1: 1, 4: 1}

        pairs = 0  # 최대 쌍의 개수를 저장할 변수 초기화

        # Step 2: 해시맵의 모든 키를 순회하며 가능한 쌍을 찾음
        for key in freq.keys():
            a, b = key, k - key  # 현재 숫자와 해당 숫자와 더해 k를 만드는 숫자
            # 예제:
            # 첫 번째 순회: a = 3, b = 6 - 3 = 3
            # 두 번째 순회: a = 1, b = 6 - 1 = 5
            # 세 번째 순회: a = 4, b = 6 - 4 = 2

            # Case 1: a < b (서로 다른 숫자가 쌍을 이룸)
            if a < b:
                # 두 숫자의 빈도 중 작은 값만큼 쌍을 형성 가능
                pairs += min(freq[a], freq[b])
                # 예제: nums = [1, 2, 3, 4], k = 5
                # a = 1, b = 4
                # freq[1] = 1, freq[4] = 1
                # pairs += min(1, 1) = 1

            # Case 2: a == b (같은 숫자가 쌍을 이룸)
            elif a == b:
                # 같은 숫자끼리 쌍을 이루려면 빈도를 2로 나눈 몫만큼 쌍을 형성 가능
                pairs += freq[a] // 2
                # 예제: nums = [3, 3, 3, 4], k = 6
                # a = 3, b = 6 - 3 = 3
                # freq[3] = 3
                # pairs += 3 // 2 = 1

        # Step 3: 결과 반환
        return pairs  # 모든 가능한 쌍의 개수 반환


# 예제 시뮬레이션
# 입력: nums = [3, 1, 3, 4, 3], k = 6
# 1. freq = {3: 3, 1: 1, 4: 1}
# 2. 첫 번째 순회: a = 3, b = 3
#    - a == b: freq[3] // 2 = 3 // 2 = 1
#    - pairs = 1
# 3. 두 번째 순회: a = 1, b = 5
#    - b는 freq에 없음 → 쌍 형성 불가
# 4. 세 번째 순회: a = 4, b = 2
#    - b는 freq에 없음 → 쌍 형성 불가
# 출력: 1

아이디어 3: 투 포인터 접근법

1. 배열을 정렬한 후, 양쪽 끝에서 시작하는 두 포인터를 사용.
2. 두 포인터가 가리키는 숫자의 합이:
   • k 보다 크면 오른쪽 포인터를 왼쪽으로 이동.
   • k 보다 작으면 왼쪽 포인터를 오른쪽으로 이동.
3. 장점:
   • 시간 복잡도 전체 O(nlog⁡n), 정렬 포함
     • O(nlogn): 배열 정렬 비용.
     • O(n): 투 포인터 순회.
   • 추가 공간 사용 X -> 공간 복잡도 O(1).

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        # Step 1: 배열을 정렬하여 두 포인터 기법을 적용 가능하게 만듦
        nums.sort()  # 정렬 후 작은 값부터 오른쪽으로, 큰 값은 왼쪽으로 줄어듦
        left = 0  # 왼쪽 포인터, 배열의 시작
        right = len(nums) - 1  # 오른쪽 포인터, 배열의 끝
        operations = 0  # 최대 쌍의 개수를 저장하는 변수

        # Step 2: 두 포인터를 활용하여 쌍 찾기
        while left < right:  # 두 포인터가 교차할 때까지 반복
            total = nums[left] + nums[right]  # 두 포인터가 가리키는 값의 합

            if total == k:  # 합이 k인 경우
                operations += 1  # 쌍을 찾았으므로 연산 횟수 증가
                left += 1  # 왼쪽 포인터 이동 (현재 값 사용 완료)
                right -= 1  # 오른쪽 포인터 이동 (현재 값 사용 완료)
            elif total < k:  # 합이 k보다 작은 경우
                # 왼쪽 포인터를 이동하여 더 큰 값을 포함시키려고 시도
                left += 1
            else:  # total > k, 합이 k보다 큰 경우
                # 오른쪽 포인터를 이동하여 더 작은 값을 포함시키려고 시도
                right -= 1

        # Step 3: 결과 반환
        return operations

 

추천 풀이

1. 입력 배열 크기가 작거나 중간 수준: 해시맵 풀이가 직관적이고 효율적.
2. 배열 크기가 크고 추가 메모리를 최소화하려는 경우: 투 포인터 접근법이 적합.

---

시간 및 공간 복잡도 비교

방법	시간 복잡도	공간 복잡도
해시맵	O(n)	O(n)
투 포인터	O(nlog⁡n)	O(1)

---

결론

• 빠르고 간결한 풀이: 해시맵을 활용한 방법.
• 추가 공간을 최소화하는 풀이: 투 포인터 접근법.

 

현재, 나는 투 포인터가 좀더 이해하기 쉽고, 이 솔루션이 속도 도 더 빠름!