Python으로 푸는 LeetCode 373. Find K Pairs with Smallest Sums

LeetCode 373. Find K Pairs with Smallest Sums

이 문제는 정렬된 두 배열(nums1, nums2)에서 원소를 한개씩 뽑았을 때, 

그 합이 작은 순서대로 k개 만큼 두 조합을 반환하는 문제이다. 

LeetCode 문제 바로 가기

LeetCode에서 푼 문제 리스트 보기

github에서 코드 보기

주의할 사항

배열에서 중복된 값이 있다는 사실을 간과한다면 결과 값이 잘못 나올 수 있다.

nums1 =[1,1,2]  nums2=[1,2,3]  k=2

output : (1,1), (1,1)

Related Topic

Heap

문제 풀이

미리 말하지만 내가 푼 코드는 효율이 좋지 못하다.  itertools.product를 사용하여 두 배열에서 원소들을 꺼내 만들 수 있는 조합을 만들면서 그 합을 조합값 안에 넣어주었다. 

그 다음에 그 합을 기준으로 재정렬한 후, k개의 수만큼 합의 수를 제외하고 반환하였다.

리뷰

leetcode의 좋은 점은 내가 다른 사람들이 제출한 코드에 비해 시간이 얼마나 걸리는지 비교가 가능하다는 점이다. 수치로만 보아도 내가 짠 코드는 개선해야 하는 요소가 많다. 

related topic이 heap인데도 heap을 활용해서 문제를 풀지 않았다. 시간을 제한해두고 풀지 않았다면 검색을 충분히 해보고 더 좋은 코드를 짤 수 있었다고 생각한다.

heap에 대해서 알아보고 문제를 다시 풀어보아야겠다.

파이썬 코드

 
import itertools
 
def kSmallestPairs(nums1, nums2, k):
    Pairs = []
    for com in itertools.product(*[nums1, nums2]):
        sumCom = sum(com)
        Pairs.append([com, sumCom])
    Pairs.sort(key=lambda item:item[1])
    Pairs = Pairs[:k]
    return [pair[0] for pair in Pairs]
 
 
 
kSmallestPairs([1,2,4,5,6],[3,5,7,9], 3) # [[1,3],[2,3],[1,5]]
kSmallestPairs([1,7,11],[2,4,6], 3) # [[1,2],[1,4],[1,6]]
kSmallestPairs([1,1,2],[1,2,3], 2) # [1,1],[1,1]
kSmallestPairs([1,2],[3], 3) # [1,3],[2,3]

#leetcode find with smallest sums #leetcode python #LeetCode 373. Find K Pairs with Smallest Sums #LeetCode 373 #leetcode 373 #leetcode heap #Find K Pairs with Smallest Sums #Python으로 푸는 LeetCode 373. Find K Pairs with Smallest Sums #python  Find K Pairs with Smallest Sums #Python  Find K Pairs with Smallest Sums # Find K Pairs with Smallest Sums Python #파이썬 leetcode 373