Smallest Range Covering Elements from K Lists
https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/editorial/
문제 파악 [필수 작성]
문제이해
각 리스트내의 원소를 최소하나는 포함하게끔 만드는 최소 범위를 찾아라
근데, 만약 범위크기가 같으면,
시작위치가 더 작은것이 더 작은 범위로 인식됨
제한 조건 확인
k개의 서브리스트가 있음
k는 최대 3500개
각 리스트내의 원소갯수는 최대 50개
최대 전체 원소갯수는 50*3500 -> 17만5천개
각 숫자는 -10만~10만까지
이미 오름차순으로 정렬되어 있음 -> 이진탐색 활용가능하다는 의미
아이디어
우선 각 리스트에 포함되는지 안되는지만 알면되기 때문에 (list 의 in 연산 시간복잡도 알아보기 & set 으로 바꾸는데 시간복잡도 알아보기)
list를 set 으로 바꿔서 생각해볼 수 있음
결국 정답인 [a,b] 는 a와 b가 결국 특정리스트중 원소일 수 밖에 없음
[ 1번 아이디어 ]
각 리스트원소 xi와 해당 리스트의 번호 ki 를 (xi,ki) 형식으로 힙에 삽입
모든 원소에 대해서 진행
그리고 순차적으로 1개씩 뽑음
뽑을때마다 min 값과 max 값을 업데이트
-> 시간초과 폐기
[ 2번 아이디어 ]
딱히 생각안나서 작은 케이스부터 순차적으로 생각시작
리스트가 1개일때는 가장 작은 숫자 a를 기준으로 [a,a] 가 정답
리스트가 2개일때는 1번 리스트원소와 2번 리스트원소의 순차적으로 순회하면서
그 차를 구함
두 리스트원소중 더 작은 리스트에서 다음원소를 탐색
만약 차가 더 작아지면 결과범위 업데이트
리스트가 3개일때도 동일하게 가능
시간복잡도 -> 각 리스트 길이만큼 순회하면 가능 즉, 최대 50*3500
아이디어는 맞는데 구현이 너무 복잡해서 포기
[ 3차 아이디어 (1시간10분 소요) ]
min_heap, max_heap 두개를 만들어서 관리하기
각 리스트들을 deque 로 초기화화고
각 리스트에서 첫번째 원소를
각각 min_heap 과 max_heap 에 초기 0번째 값들을 다 넣어줌
min_heap 헤드와 max_heap 헤드를 비교해서 업데이트
만약 이제껏 본것중 그 차가 제일 작으면 min과 max를 결과 range 로 저장
min_heap 에서 pop하고 pop한 값에 해당하는 리스트에서 해당 값을 popleft 해서 지워준 후
해당 리스트에서 다음원소를 min_heap 과 max_heap에 각각 넣음
(만약 같다면, 그냥 처음먼저 본 리스트의 다음원소를 넣음)
(만약 리스트에서 빼려했는데 리스트 길이가 1이라면 루프도는걸 멈춤)
이 아이디어는 힙을 굳이 안써도 될지도???
4차 아이디어 ()
한방에 통과는 했지만 효율성이 떨어져서
3차 아이디어를 heap 을 안쓰고 구현
시간복잡도
1번 아이디어
175,000*3,500 = 6억 -> 시간초과
2번 아이디어
17만5천
자료구조
접근 방법 [필수 작성]
코드 구현 [필수 작성]
1차 시도
한방에 통과
그러나 효율성이 똥이다.
어떻게 하면 효율성을 개선할 수 있을까?
import sys
import heapq
from collections import deque
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
INF = sys.maxsize
k = len(nums)
tmp_min = INF
tmp_max = -INF
tmp_diff = INF
min_heap = []
max_heap = [] #max_heap 에 넣을때는 음수로 변환 후 넣어야함
deque_list = []
for l in nums:
deque_list.append(deque(l))
heapq.heappush(min_heap,l[0])
heapq.heappush(max_heap,l[0]*(-1))
tmp_diff = max_heap[0]*(-1) - min_heap[0]
result = [min_heap[0], max_heap[0]*(-1)]
flag = 0
while True:
if flag == 1:
break
for i in range(k):
if min_heap[0] == deque_list[i][0]:
if len(deque_list[i]) > 1:
deque_list[i].popleft()
heapq.heappop(min_heap)
heapq.heappush(min_heap,deque_list[i][0])
heapq.heappush(max_heap,deque_list[i][0]*(-1))
if tmp_diff > max_heap[0]*(-1) - min_heap[0]:
tmp_diff = max_heap[0]*(-1) - min_heap[0]
result = [min_heap[0], max_heap[0]*(-1)]
else:
flag = 1
break
return result
2차 시도(개선한 코드)
최솟값이 몇번째 리스트에 포함되어있는지 미리 기록을 해두는 것으로 최적화를 했다.
import sys
import heapq
from collections import deque
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
INF = sys.maxsize
k = len(nums)
for i in range(len(nums)):
for j in range(len(nums[i])):
nums[i][j] = (nums[i][j],i)
tmp_min = INF
tmp_max = -INF
tmp_diff = INF
min_heap = []
max_heap = [] #max_heap 에 넣을때는 음수로 변환 후 넣어야함
deque_list = []
for l in nums:
deque_list.append(deque(l))
heapq.heappush(min_heap,l[0])
heapq.heappush(max_heap,(l[0][0]*(-1),l[0][1]))
tmp_diff = max_heap[0][0]*(-1) - min_heap[0][0]
result = [min_heap[0][0], max_heap[0][0]*(-1)]
flag = 0
while True:
if flag == 1:
break
idx = min_heap[0][1]
if len(deque_list[idx]) > 1:
deque_list[idx].popleft()
heapq.heappop(min_heap)
heapq.heappush(min_heap,deque_list[idx][0])
heapq.heappush(max_heap,(deque_list[idx][0][0]*(-1),deque_list[idx][0][1]))
if tmp_diff > max_heap[0][0]*(-1) - min_heap[0][0]:
tmp_diff = max_heap[0][0]*(-1) - min_heap[0][0]
result = [min_heap[0][0], max_heap[0][0]*(-1)]
else:
flag = 1
break
return result또 여기서 max_heap도 사실상 굳이 필요가 없다.
그냥 새로운 값과 현재 max 값을 비교해주면 O(1) 인데 괜히 힙에 넣어주면 O(logN) 만큼의 시간이 소요되기 때문이다.
또, deque 로 바꾸는 과정도 굳이 필요없고 그냥 idx 를 1 증가시켜서, idx 가 len를 초과하기 전까지만 탐색해주면 된다.
그렇게하면 해설코드랑 완전히 비슷해지는 구조이기도하고, 딱히 테스트케이스에 대해서 시간이 향상되지도 않기 때문에 그냥 놔두도록 하겠다.
배우게 된 점 [필수 작성]
필요에 따라 idx 를 튜플 형태로 저장해주는 테크닉
질문 [ 필수 X ]
댓글로 또는 이곳에 질문 남겨주세요.
