632. Smallest Range Covering Elements from K Lists

Problem : https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists

 

Difficulty : Hard

 

Status : Solved

 

Time : 00:18:12

 

---

 

문제 설명

 

k개의 단조증가하는 순서(감소하지 않는 순서)로 정렬된 리스트를 가지고 있다. k개의 리스트 각각의 적어도 하나의 수를 포함하는 가장 작은 범위를 구하여라.

 

우리는 다음 상황 ( b-a < d-c 거나, b-a == d-c이면서 a<c일때) 범위 [a, b]가 범위 [c, d]보다 작다고 정의한다.

---

 

풀이

 

쪼오금 마음에 안드는 풀이긴 하지만, 이렇게 풀 수 있다! 를 보려주려고 한다.

 

슬라이딩 윈도우를 생각해 보자. 이 슬라이딩 윈도우는 가급적 k개 집합의 모든 수를 최소한으로 보유하는 게 목적이다. 즉 다음 기능이 필요하다.

• 숫자와 인덱스 정보를 저장할 큐
• 덱에 각 리스트의 숫자를 얼마나 보유하고 있는지 저장할 리스트

 

또한, 우리는 입력받은 k개 리스트를 하나로 합치고 정렬할 것이다(이 때 각 숫자는 원본 리스트의 정보를 가지고 있다 - 즉 숫자, 리스트 번호 형태의 튜플이라고 생각하자)..

 

이제 nums를 순회할 텐데, 다음 과정을 수행한다.

• 슬라이딩 윈도우 큐에 nums와 index 정보를 추가한다.
• 슬라이딩 윈도우가 커버 조건(k개의 모든 리스트의 숫자를 모두 보유하고 있는지)을 만족하지 않을 때까지, 슬라이딩 윈도우 큐를 pop한다.
• 마지막 pop 직전의 구간이 정답 후보가 될 수 있는 구간(오른쪽에 num, idx일 때의 최소 구간)이므로, 최소 구간을 비교하며 확인한다.

k <= 3500, 한 리스트의 길이 <= 50이므로 한 번의 순회로 충분히 짧은 시간 내에 정답을 얻을 수 있다.

 

풀이 코드

class SlidingWindow:
    def __init__(self, k):
        self.total = 0
        self.count = [0]*k
        self.k = k
        self.queue = deque()
    def push(self, num, idx) :
        if not self.count[idx] :
            self.total += 1
        self.count[idx] += 1
        self.queue.append((num, idx))
    def pop(self) :
        num, idx = self.queue.popleft()
        self.count[idx] -= 1
        if not self.count[idx] :
            self.total -= 1
    def coverLength(self) :
        if not self.total == self.k :
            return [-1, -1]
        return [self.queue[0][0], self.queue[-1][0]]

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        k = len(nums)
        slidingWindow = SlidingWindow(k)
        nums = [(i, j) for j in range(k) for i in nums[j]]
        nums.sort()
        result = [nums[0][0], nums[-1][0]]

        for num, idx in nums :
            slidingWindow.push(num, idx)
            minLen = [-1, -1]
            while True :
                tmp = slidingWindow.coverLength()
                if tmp == [-1, -1] :
                    break
                minLen = tmp
                slidingWindow.pop()
            if minLen != [-1, -1] and minLen[1] - minLen[0] < result[1] - result[0] :
                result = minLen
        return result