[leetcode]373.find-k-pairs-with-smallest-sums

📃문제 설명

nums1과 nums2에서 각각 하나씩 숫자를 짝지은 후, k개 만큼 return값으로 반환한다.
단 조합의 합이 작은 순서대로 반환해야한다.

🖊풀이 1

우선 2중 for문을 돌면서 가능한 조합이 담긴 리스트를 만들어 준다.
그 후 lambda 함수를 활용하여 조합의 합이 작은 순서로 리스트를 정렬해준다.

위의 방법을 사용하면 효율이 좋지않아서 메모리 초과를 반환한다.

시간 복잡도는 O(NM) + O(NlogN)
( 파이썬의 정렬 라이브러리는 최악의 경우에도 O(NlogN) 보장 )

🖊풀이 2

heap을 사용하여 문제를 풀어보자

heap은 우선순위 큐를 사용한 자료 구조로, 최소값이나 최대값을 빠르게 찾을 수 있다.
힙은 완전 이진 트리의 일종으로 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같은 형태를 가진다.
힙트리는 중복된 값을 허용한다. (이진 탐색 트리는 중복 허용 X)

메모리를 초과하지 않으려면 저장하는 데이터의 갯수를 줄여야한다.
k개 이상의 조합을 저장할 필요가 없으므로 루프를 도는 조건으로 추가해준다.

시간 복잡도는 O(N) > 2중 반복문을 돌지 않아도 되기때문