[LeetCode 리트코드] Max Number of K-Sum Pairs, python

문제

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.

(해설)

int배열 nums와 int k가 주어진다. nums의 두 숫자를 골라 더해서 k가 되면 nums에서 삭제한다. 이렇게 k를 만들 수 있는 쌍의 최대값을 구하여라. 

예

Input: nums = [1,2,3,4], k = 5

Output: 2

• 1,4 그리고 2, 3

추가사항

 

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109

 

 

나의 솔루션

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        dic = {}
        result = 0
        for n in nums:
            if n in dic.keys():
                dic[n] += 1
            else:
                dic[n] = 1
        for key in dic.keys():
            if key < (k+1) // 2 and k-key in dic.keys():
                result += min(dic[key], dic[k - key])
        if k % 2 == 0 and k // 2 in dic.keys():
            result += dic[k // 2] // 2
        return result
                

 

깨달은 점

처음에 count array를 만들어서 nums의 값들을 count에 넣었다. ( for num in nums: count[num] += 1)

그런데 타임아웃..... 심지어 count array를 만드는 코드만 넣었는데도 그냥 타임아웃이 났다. 그래서 할수없이 딕셔너리를 썼는데 그건 또 통과했다........ python 내부 코드가 어떻게 돌아가는지 더 공부를 해야겠다.

 

결과

Submission Detail