1679. Max Number of K-Sum Pairs

Max Number of K-Sum Pairs - LeetCode

 

한 연산에서 배열에서 합이 k가 되는 두 숫자를 선택하고, 해당 숫자들을 배열에서 제거할 수 있습니다.
배열에서 수행할 수 있는 최대 연산 횟수를 반환하세요.

 

 

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.

 

 

문제 요약:

주어진 배열에서 합이 k가 되는 숫자 쌍을 찾아내고, 해당 숫자 쌍을 제거할 수 있는 최대 연산 횟수를 찾는 문제입니다.

풀이과정:

주어진 배열 nums를 순회하면서 합이 k가 되는 숫자 쌍을 찾아내야 합니다. 이를 위해 다음과 같은 절차를 따릅니다:

1. 숫자 쌍을 저장할 데이터 구조를 생성합니다. 이를 위해 해시 맵(HashMap)을 사용합니다. 이 해시 맵은 숫자를 키(key)로 사용하고, 해당 숫자가 몇 번 등장했는지를 값(value)으로 저장합니다.
2. 주어진 배열 nums를 순회하면서 다음을 수행합니다:
   - 현재 숫자 num과 k 사이의 차이 diff를 계산합니다. (diff = k - num)
   -  해시 맵에서 diff를 찾아서, 해당 숫자가 남아있는지를 확인합니다. 만약 남아있는 경우, 연산을 수행할 수 있으므로 연산 횟수를 증가시키고, 해당 숫자의 카운트를 감소시킵니다.
3. 순회가 끝나면 연산 횟수를 반환합니다.
   이런 방식으로 주어진 배열에서 합이 k가 되는 숫자 쌍을 찾아내고, 최대 연산 횟수를 구할 수 있습니다. 이 알고리즘은 선형 시간(O(n))에 문제를 풀 수 있습니다. 

class Solution {
    public int maxOperations(int[] nums, int k) {
        int removeCnt = 0;
        HashMap<Integer, Integer> hM = new HashMap<>();

        for(int num : nums){
            hM.put(num, hM.getOrDefault(num, 0) + 1);
        }

        for(Integer num : hM.keySet()){
            int num2 = k - num;
            
            if(hM.containsKey(num2) && hM.get(num2) > 0 && hM.get(num) > 0){
                if(num == num2){
                    int minCount = hM.get(num) /2;
                    hM.put(num, minCount);
                    removeCnt += minCount;
                }else{
                    int minCount = Math.min(hM.get(num), hM.get(num2));
                    hM.put(num, hM.get(num) - minCount);
                    hM.put(num2, hM.get(num2) - minCount);
                    removeCnt += minCount;
                }
            }
        }
        return removeCnt;
    }
}