Game Tech Blog
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 를 증가시키면 단순히 해결할 수 있는 문제였다.
앞으로 투포인터 문제에선 일단 해보고 안되면 정렬한 후에 넣어보는 것도 시도해봐야겠다.
물론 원리에 대한 정확한 이해가 선행되어야한다.
반응형
'Algorithm > LeetCode' 카테고리의 다른 글
283. Move Zeroes (0) | 2023.07.25 |
---|---|
11. Container With Most Water (0) | 2023.07.24 |
392. Is Subsequence (0) | 2023.07.20 |
443. String Compression (0) | 2023.07.18 |
334. Increasing Triplet Subsequence (2) | 2023.07.17 |
Comments