[LeetCode] 1679. Max Number of K-Sum Pairs

1. 문제 이해

정수 리스트 nums와 정수 k가 주어진다.

한 번의 작업에서, 리스트에서 합이 k인 두 숫자를 선택하여 리스트에서 제거할 수 있다.

리스트에서 수행할 수 있는 작업의 최대 횟수를 리턴한다.

 

 

2. 풀이 과정

리스트를 오름차순으로 정렬한다.

리스트의 처음과 끝을 가리키는 투 포인터를 만든다.

while 문을 사용해 start < end일 때 반복한다.

현재 start, end에서 합이 k라면 cnt 변수를 1만큼 증가시킨다. start와 end도 각각 1만큼 증가시키고 감소시킨다.

만약 합이 k보다 작다면 start만 1만큼 증가시킨다. k보다 크다면 end만 1만큼 감소시킨다.

 

 

3. 전체 코드

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        nums.sort()
        start, end = 0, len(nums) - 1
        cnt = 0
        while start < end:
            if nums[start] + nums[end] == k:
                cnt += 1
                start += 1
                end -= 1
            elif nums[start] + nums[end] < k:
                start += 1
            else:
                end -= 1
        
        return cnt

 

 

4. 생각할 점

- 처음에는 합이 k인 경우 리스트에서 실제로 pop()을 통해 요소를 제거했다. 하지만 인덱스가 당겨지는 문제가 있었고 포인터만 옮기면 되므로 실제로 요소를 제거할 필요가 없다.

 

 

5. 출처

- https://leetcode.com/problems/max-number-of-k-sum-pairs/?envType=study-plan-v2&envId=leetcode-75