LeetCode[ 373 | Python ] Find K Pairs with Smallest Sums
업데이트:
문제
정수로 이루어진 배열 nums1과 nums2 에서 각각의 원소에 대해 그 합이 가장 작은 짝을 주어진 k개 만큼 반환해야하는 문제.
풀이
끔찍하고 신나는 경험을 했던 문제였다.
끔찍하고 신나는 경험
언뜻 이해하기 쉬운 문제이며 그 구현도 간단할 것 같았지만 그렇지 않았다.
정답
실행시간 : 3342ms
메모리 : 30.5MB
nums1에 대해 순회한다.- 이 때
k보다 크지 않으면k만큼 순회한다. nums2에 대해 순회한다.- 이 때
k보다 크지 않으면k만큼 순회한다. 이는 아무리 배열이 길어봐야 오름차순으로 정렬되어 있고, k*k 이상으로 탐색해봐야 그전에k개의 결과가 나오기 때문이다. heap의 크기가k보다 작은 경우 두 원소의-를 취한 값,nums1의 원소,nums2의 원소를 리스트로 저장한다.heap의 크기가k보다 크거나 같은 경우- 현재 탐색하고 있는 원소의 합이
heap안의 최대 값보다 크다면 해당 반복문에서 탈출한다.- 이는 탐색하고 있는 값이 이미
heap최대 값보다 크다면 오름차순으로 정렬된 배열 내에서는 더 큰 값 밖에 나올 수 없기 때문이다. heap에서heappop을 통해 원소를 하나 꺼낸 뒤-를 취해 원래의 값으로 되돌려 저장한다.- 이는 메모리 제한을 해결하기 위함이다.
- 이는 탐색하고 있는 값이 이미
- 현재 탐색하고 있는 원소의 합이
- 이 때
- 이 때
import heapq
class Solution(object):
def kSmallestPairs(self, nums1, nums2, k):
heap = []
for i in range(min(k, len(nums1))):
for j in range(min(k, len(nums2))):
if len(heap) < k:
heapq.heappush(heap, [-(nums1[i] + nums2[j]), nums1[i], nums2[j]])
else:
if nums1[i] + nums2[j] > -heap[0][0]:
break
heappushpop(heap,[-(nums1[i]+nums2[j]),nums1[i],nums2[j]])
return list(map(lambda x : x[1:], heap))
시도했던 코드에서의 메모리를 해결하기 위해 짠 솔루션이기 때문에 억지로 해결한 듯한 느낌이 드는 코드라고 생각이 들었다.
더이상 개선할 포인트를 찾지 못해서 다른 이의 솔루션을 참고했다.
참고한 솔루션
By - StefanPochmann
값을 직접 이용하지 않고 인덱스를 이용했다.
heappop연산을 통해 가장 합이 작은 값들의 인덱스들을 뽑아내고 이를통해 인덱스를 조작하기 때문에 자연스레 가장 작은 값들의 합을 pairs에 채워넣게 되는 코드이다.
소요 시간은 800ms대, 사용 메모리는 30MB 정도로 둘 모두 성능이 훌륭했다.
def kSmallestPairs(self, nums1, nums2, k):
queue = []
def push(i, j):
if i < len(nums1) and j < len(nums2):
heapq.heappush(queue, [nums1[i] + nums2[j], i, j])
push(0, 0)
pairs = []
while queue and len(pairs) < k:
_, i, j = heapq.heappop(queue)
pairs.append([nums1[i], nums2[j]])
push(i, j + 1)
if j == 0:
push(i + 1, 0)
return pairs
시도
우선 두 배열의 원소와 합을 heap에 저장하여 차례대로 합에 따라 빼내고자 했다.
하지만 각 원소의 입력이 10000이 될 수 있으므로 한 배열이 총 100만개의 원소를 가질 수 있게 된다.
따라서 메모리 초과로인해 코드가 실행되지 않았다.
다른 시도들도 해봤으나, 가장 간단한 로직이 옳다고 생각되어 이 로직을 토대로 개선하고자 했다.
import heapq
class Solution(object):
def kSmallestPairs(self, nums1, nums2, k):
heap = []
for i in range(len(nums1)):
for j in range(len(nums2)):
heapq.heappush(heap, [nums1[i] + nums2[j], nums1[i], nums2[j]])
res = []
for _ in range(k):
if not heap:
break
res.append(heappop(heap)[1:])
return res
생각 & 정리
문제를 풀고나서 다른 이들의 솔루션을 한번씩 보는데, 정말 훌륭한 솔루션들이 많다.
하루종일 생각하고도 별 솔루션이 안나오는 경우가 많은데 한 사람이 여러개의 솔루션을 가지고 설명하는 경우도 허다하게 보이는 것 같다.
한 문제를 정해놓은 해결방법으로 접근하는 것은 피해야한다고 생각하고 때로는 코드를 완전히 지우고 다시 생각하거나, 반대로 생각한대로 고집스럽게 구현을 하고는 한다.
이러한 경험이 하나둘 쌓여가 다양한 솔루션을 낼 수 있는 사람이 될 것이라고 생각이 들었다.
댓글남기기