[Two Pointers][Medium] 1679. Max Number of K-Sum Pairs

https://leetcode.com/problems/max-number-of-k-sum-pairs/description

Max Number of K-Sum Pairs - LeetCode

 

Q. 배열에서 두 수의 합이 sum이 되면 두 수를 제거한다. 이 연산의 최대수를 구하라.

 

Solution. 

  두수의 합이 배열과 연관지어지면, 보통 hash를 사용한다. 해당 수에서 어떤 수가 더해지면 sum이 될지 hash에 저장하고, 관련수가 나오면 빠르게 검색 가능하므로, 결과적으로 한번의 loop 순회연산만 필요하게 된다. O(N)의 TC.

 

int maxOperations(vector<int>& nums, int sum)
{
    // nums 배열에서 두 수의 합이 sum이 되면 두 수를 제거한다.
    // 이 연산의 최대 수를 구하라.
    // 
    int ret = 0;
    unordered_map<int, int> freqMap;
    for (int k = 0; k < nums.size(); ++k)
    {
        if (freqMap.find(nums[k]) == freqMap.end())
            freqMap[sum - nums[k]]++;
        else
        {
            --freqMap[nums[k]];
            if (freqMap[nums[k]] == 0)
                freqMap.erase(nums[k]);
            ++ret;
        }
    }
    return ret;
}

 

 

Comment : Submit 하고 봤더니 결과의 TC 순위가 그닥 좋지 않다.

 다른 solution을 찾아봤는데, 정렬하고 두개의 포인터를 사용하여 좁히는 방법을 썼다. 

 일단 정렬하는데서 O(N x Log(N))을 쓰는데, 어째서인지 결과는 이 방법이 더 빠르다. 

 

 포인터로 좁혀서 실제적으로 O(N/2) 를 쓴다고 하더라도 조금 의아스런 결과. 

 map search에 생각보다 실제로 시간을 더 쓴다는 것인가 싶기도 하다.

 

정렬하는 solution 

 int maxOperations(vector<int>& nums, int sum) 
 {
 	sort(nums.begin(), nums.end());
    int l = 0, r  = nums.size() - 1;
    int ans = 0;
    while(l < r) {
        if (nums[l] + nums[r] == sum) {
            ans++;
            l++;
            r--;
        }
        else if (nums[l] + nums[r] < sum) l++;
        else r--;
    }
    return ans;
}