04/09 코딩테스트 문제풀이 - 632. Smallest Range Covering Elements from K Lists (Leetcode) ⭐⭐⭐⭐⭐

문제

• Leetcode 알고리즘 문제
• 632. Smallest Range Covering Elements from K Lists
• 문제 내용 : [링크]
  
  

---

내가 작성한 코드

import sys
from heapq import heappush, heappop

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:

        # 인덱스를 활용하기 위해 nums 전처리
        for i in range(len(nums)):
            nums[i] = [[val, i] for val in nums[i]]

        # 초기값 세팅
        pq = []
        max_val = -sys.maxsize
        index_list = [0]*len(nums)

        for i in range(len(nums)):
            heappush(pq, nums[i][0])
            max_val = max(max_val, nums[i][0][0])

        answer = [pq[0][0], max_val]
        
        # pq에서 heappop을 해주면서 최소 범위 찾아나감 임의의 nums[i]의 원소를 모두 사용한 경우 break
        while True:
            min_val, idx = heappop(pq)
            index_list[idx] += 1

            if index_list[idx] == len(nums[idx]):
                break

            next_num = nums[idx][index_list[idx]]
            heappush(pq, next_num)
            max_val = max(max_val, next_num[0])

            if max_val - pq[0][0] < answer[1] - answer[0]:
                answer = [pq[0][0], max_val]

        return answer 
          

---

풀이방향

• nums의 모든 리스트들의 최소 1개 원소 이상 포함할 수 있는 최소 range를 찾는 문제이다.

• nums의 각 리스트에서 최소 1개의 요소는 포함해야하므로, nums[i]의 초기값들을 heappush하고, max_val을 업데이트 하여 첫 answer 값을 설정해준다.

• 즉, 모든 nums[i]의 초기 값을 포함할 수 있는 범위를 answer로 설정해주고, 이 answer의 범위를 줄여나가는 방법으로 문제를 해결한다!

---

풀이

• 먼저 nums를 인덱스 정보와 같이 활용할 수 있도록 전처리 해준다. [val, i]의 형태로 변형해준다.

• 우선순위 큐 pq, 최대값 max_val, 각 nums[i]의 인덱스를 확인할 수 있는 index_list를 설정한다.

• nums의 리스트들을 탐색하면서, nums[i]의 초기값들을 pq에 heappush하고, max_val을 업데이트 해준다.

• 초기 범위를 answer에 저장한다.

• answer의 범위를 줄여나가기 위해 다음 과정을 반복한다.

1. pq에서 heappop을 통해 min_val, idx를 추출한다.

2. heappop 해주었으므로, index_list[idx]를 1 증가시킨다.

3. 업데이트 된 인덱스에 따른 nums[idx][index_list[idx]] 를 next_num에 반영한다.

4. next_num을 pq에 heappush 해준다.

5. max_val을 업데이트 해준다.

6. 현재 answer와 [pq[0][0], max_val]를 비교하여, 범위의 길이가 더 짧은 값을 answer에 업데이트 해준다.

7. 임의의 nums[i] 인덱스가 len(nums[i])와 같아질 때 반복을 중단한다.

• answer를 출력한다.

---

⭐⭐⭐⭐⭐

• answer 범위의 최소값을 해당 값이 포함된 리스트의 다음값으로 업데이트 해줄 때, 우선순위 큐를 활용하는 문제였다.

• minheap 구조를 통해 최소값을 활용하는 방법과, max_val을 업데이트 해나가는 과정을 공부해두자.

• 이 문제처럼, 리스트들에서 순서대로 작업이 이루어지지 않는 경우, 해당 요소의 리스트 출처를 편하게 이용하기 위한 인덱스를 포함하여 구조화하는 방법을 연습하자.