[LeetCode] 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 <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9

 

1 이상의 숫자만 들어 있는 배열 nums와 양수 k가 주어진다.

이 때 nums 안에서 두 개의 임의의 수를 더해 k가 되는 쌍의 수를 중복 없이 구하는 문제.

 

문제 풀이

var maxOperations = function (nums, k) {
  let operations = 0;

  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] >= k) {
      continue;
    }
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] >= k) {
        continue;
      }
      if (nums[i] + nums[j] == k) {
        nums[i] = k
        nums[j] = k;
        operations++;
        break;
      }
    }
  }
  return operations;
};

 

우선 이중 for문으로 처리했다. 

nums 내의 숫자는 1 이상이므로, nums[i] 또는 nums[j]가 k와 같거나 더 크면 해당 수는 넘어가도록 설정했다.

그리고 nums[i]와 nums[j]를 더해 k가 되면 답이 될 operations에 1을 더해 주고,

해당 i에서 한 쌍을 찾았으므로 break한 후 그 다음으로 넘어간다. 이 때 그 쌍의 값은 각각 k로 변경해 준다.

처음에는 nums.includes(nums[i]) 와 같이 처리하려고 했는데, includes 함수 자체도 시간이 많이 들 것 같아서 이렇게 처리했다.

 

근데 아니나다를까, 51개의 테스트케이스 중에서 48개까지는 잘 넘어갔지만...

49번째부터 엄청난 수의 배열이 제시됐고, 시간 제한 초과로 제출이 되지 않았음^_ㅠ

 

아무튼 또 Solution을 참고해서... 

 

const maxOperations = function (nums, k) {
  let operations = 0;
  const countMap = {};

  for (let num of nums) {
    const complement = k - num;
    if (countMap[complement] > 0) {
      operations++;
      countMap[complement]--;
    } else {
      countMap[num] = (countMap[num] || 0) + 1;
    }
  }

  return operations;
};

 

이렇게 하니 해결이 됐다^_ㅠ

Two pointers라는 카테고리에 너무 집착한 나머지 set같은 수단은 전혀 생각하지 못했던 게 문제인 것 같다.

그렇다해도 이런 식의 활용은 생각지 못했을 것 같지만... javascript에서 set을 쓸 생각을 전혀 안 해봤던 것도 문제고..

 

여기다 k가 1이거나 nums의 길이가 1인 경우는 그냥 0을 리턴하면 좀 더 빨라질 듯.