[LeetCode] LeetCode 1679. Max Number of K-Sum Pairs 해설 및 풀이 (Python)

LeetCode 1679. Max Number of K-Sum Pairs

https://leetcode.com/problems/max-number-of-k-sum-pairs/description/?envType=study-plan-v2&envId=leetcode-75

 

---

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 <= 105
1 <= nums[i] <= 109
1 <= k <= 109

 

한글 해석

 

정수 배열 nums과 정수 가 주어졌습니다 k.

한 번의 작업으로 배열에서 합이 같은 두 숫자를 선택하여 k배열에서 제거할 수 있습니다.

배열에서 수행할 수 있는 최대 작업 수를 반환합니다 .

 

예시 1:

입력: nums = [1,2,3,4], k = 5
 출력: 2
 설명: nums = [1,2,3,4]로 시작합니다.
- 숫자 1과 4를 제거하면 nums = [2,3]이 됩니다.
- 숫자 2와 3을 제거한 후 nums = []
합이 5가 되는 쌍이 더 이상 없으므로 총 연산은 2개입니다.
예 2:

입력: nums = [3,1,3,4,3], k = 6
 출력: 1
 설명: nums = [3,1,3,4,3]으로 시작합니다.
- 처음 두 개의 3을 제거하면 nums = [1,4,3]이 됩니다.
합이 6이 되는 쌍이 더 이상 없으므로 총 연산은 1개입니다.
 

제약 조건:

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 109

---

문제 유형

배열 Array

해시 테이블 Hash Table

투 포인터 Two Pointers

정렬 Sorting

 

풀이 방법 도출

 

배열 nums와 정수 k가 주어지고 두 수의 합이 k가 되는 쌍이 최대 몇 개 만들 수 있는지를 구하는 문제입니다.

한 숫자는 한 번만 쓸 수 있습니다.

 

1. 숫자별로 몇 번 등장하는지 세기 위해 Counter 라이브러리를 사용합니다.
2. 각 숫자 num에 대해 k - num이 존재하는지 확인합니다.
3. num과 k - num 모두 존재한다면 가능한 쌍의 개수는 두 숫자의 등장 횟수 중 작은 값 (min(count[num], count[k - num]))입니다.
4. num이 k - num과 같다면 등장 횟수의 절반 (count[num] // 2) 만큼 쌍을 만들 수 있습니다.
5. 사용한 숫자는 0으로 초기화해서 중복 처리를 방지합니다.

 

 

시간 복잡도

• O(N)

---

핵심 코드 삽입 및 설명

 

from collections import Counter
from typing import List

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        # 숫자별 등장 횟수 세기
        count = Counter(nums)
        operations = 0

        for num in list(count.keys()):
            complement = k - num  # 짝이 되는 수

            # 만약 짝이 존재한다면
            if complement in count:
                if num == complement:
                    # 자기 자신과 짝이 되는 경우
                    operations += count[num] // 2
                else:
                    # 다른 수와 짝이 되는 경우
                    operations += min(count[num], count[complement])

                # 짝을 맞췄으므로 둘 다 0으로 처리
                count[num] = 0
                count[complement] = 0

        return operations