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

 

[TC]

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

[접근]

문제만 보고, 맨앞 + 맨뒤 두개만 선정해서 Start,End 가운데로 모으면서 종료시키는 방식으로 구상.

추가로, & 형태로 주어진 nums 를 확인해서 문제를 Accept 주는줄 잘못알고 접근해서 remove 에 별에별거 신경다쓰다가 문제를 놓침.

아무리해도 TimeLimit 방식을 해결할 수 없어서 솔루션 몇개를 찾아본 결과, 이런답에는 정렬을 선작업으로 진행하면 된다는 공통점을 찾았고, 선 정렬 후 내가 구상했던 방식 적용.

 

[코드] - C++

#include <algorithm>

class Solution {
public: int ret = 0;
public:
    int maxOperations(vector<int>& nums, int k) {
        ret = 0;

        int l = 0;
        int r = nums.size()-1;

        sort(nums.begin(),nums.end());

        while (r > l)
        {
            if (nums[r] + nums[l] == k)
            {
                ++ret;
                --r;
                ++l;
            }
            else if (nums[r] + nums[l] > k)
                --r;
            else
                ++l;
        }


        return ret;
    }
};

 

[결과]

[시도]

[후기]

TimeLimit 를 해결할 수 없었고, 더이상 방법이 없다고 판단했을 때, 솔루션 몇개를 참고했다.

힌트는 유료라 막혀서 볼 수 없었다.

정렬을 진행한 후에 out Count 를 증가시키면 단순히 해결할 수 있는 문제였다. 

앞으로 투포인터 문제에선 일단 해보고 안되면 정렬한 후에 넣어보는 것도 시도해봐야겠다.

 

물론 원리에 대한 정확한 이해가 선행되어야한다.