632_Smallest Range
https://leetcode.com/problems/smallest-range
Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
최소 범위
오름차순으로 정렬된 k개의 리스트가 주어지고, k번째 리스트에는 정수(-100000 < elements < 100000)범위의 값들이 들어 있다.
각 리스트들 중 적어도 하나의 원소를 포함한 최소 범위를 구하는 문제이다.
다음과 같은 3가지 아이디어가 필요하다.
첫번째 아이디어
k개의 리스트를 모아두었다고 가정할때, 최소 범위를 어떻게 구할 것인지 생각해보자.
어떤 임의의 구간이 존재한다고 할때, 맨 오른쪽 위치(최고값)을 오른쪽으로 이동시키는 편이 나을까?
아니면, 맨 왼쪽 위치(최소값)를 오른쪽으로 이동시키는 편이 나을까?
답은 후자이다.
두번째 아이디어
k개의 리스트에 대한 위치를 가리키는 포인터가 필요하다.
현재 최소값이 속한 리스트(k_idx)에서 그 다음 값을 포함해서
최소거리를 계산해 보아야하기 때문이다.
세번째 아이디어
큐의 맨 앞이 최소값을 항상 유지하려면 어떤 자료구조를 사용해야할까?
정답은 min heap queue이다. 최소힙큐를 사용하면 낮은 값 부터 앞으로 정렬되어있다.
또한 튜플을 사용해서 (value, k_idx)로 힙큐에 push하면,
첫번째 인덱스인 value를 기준으로 정렬이 자동으로 되어있다.
위 아이디어를 정리하면 아래와 같다.
필요한 것들
이 문제를 풀기 위해 필요한 것들은 다음과 같다.
또한 초기 조건을 설정해주는 것이 매우 중요한데, 시작 조건은 다음과 같다.
구간의 최소값,
구간의 최대값,
구간의 좌표,
구간의 길이
4가지가 존재해야한다.
위에서 초기 heap 값은 실제로 [ (0, 1), (4, 0), (5, 2) ] 이다. 튜플은 (value, k_idx)로 되어있다.
1
value, k_idx = heapq.heappop(heap)
이제 하나씩 heapq.heappop(heap)를 해주면,
[ (4, 0), (5, 2) ] 이 된다.
이 때, pop된 튜플은 (0, 1)이다.
value값은 신경쓰지말고, k_idx를 보자. k_idx값은 1이다.
값 0 은 2번째 리스트([ 0, 9, 12, 20 ])에 있다는 의미이다.
1
k_pointer[k_idx] += 1
현재 포인터 위치(k_pointer) [ 0, 0, 0 ]에서 k_idx가 1이니까,
오른쪽으로 이동시키면(k_pointer[k_idx] += 1), [ 0, 1, 0 ] 이 된다.
1
p = k_pointer[k_idx]
k번째 리스트의 현재 위치 p를 k_pointer[k_idx] 라 가정했을때,
그리고 nums[k_idx][p] 값은 두번째 리스트의 9 값을 의미한다.
9의 값을 힙에 다시 넣어준다. (넣어준 상태에서 구간범위를 구해보기 위해서)
9의 값은 두번째 리스트 (k_idx = 1)에 있다.
1
heapq.heappush(heap, (nums[k_idx][p], k_idx))
heapq.heappush(heap, (nums[k_idx][p], k_idx))을 해주면, [ (4, 0), (5, 2), (9, 1) ] 이 된다.
이제 이 상태에서 구간의 최대최소값 등을 구해야한다.
우리는 오른쪽으로 이동시킨 값(nums[k_idx][p])이 기존의 maximum값보다 큰지 비교해서 최대값을 갱신시켜줄 필요가 있다.
1
2
if nums[k_idx][p] > maximum:
maximum = nums[k_idx][p]
구간의 최소값은 heap의 맨 앞과 같다.
1
minimum = heap[0][0]
최소값과 최대값이 구해졌으면, 최소범위값이 얼마나 되는지 계산해본다.
범위값이 기존의 값보다 작으면 갱신해주고, 해당 좌표도 기록해둔다.
1
2
3
if minimum_range_value > maximum - minimum:
minimum_range_value = maximum - minimum
minimum_range_coord = [minimum, maximum]
최종 코드는 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution(object):
def smallestRange(self, nums):
"""
:type nums: List[List[int]]
:rtype: List[int]
"""
import heapq
heap = []
maximum = float("-inf")
for idx, num_list in enumerate(nums):
heapq.heappush(heap, (num_list[0], idx))
if maximum < num_list[0]:
maximum = num_list[0]
# minimum value
minimum = heap[0][0]
minimum_range_value = maximum - minimum
minimum_range_coord = [minimum, maximum]
#print(minimum, maximum)
#print(minimum_range_coord)
#print(minimum_range_value)
k_pointer = [ 0 for i in range(len(nums)) ]
while True:
value, k_idx = heapq.heappop(heap)
k_pointer[k_idx] += 1
p = k_pointer[k_idx]
if p >= len(nums[k_idx]):
break
heapq.heappush(heap, (nums[k_idx][p], k_idx))
if nums[k_idx][p] > maximum:
maximum = nums[k_idx][p]
minimum = heap[0][0]
if minimum_range_value > maximum - minimum:
minimum_range_value = maximum - minimum
minimum_range_coord = [minimum, maximum]
return minimum_range_coord