[LeatCode] Hard 632 Smallest Range Covering Elements from K Lists (Java)

문제 링크

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

문제 설명

K개의 정렬된 리스트가 주어졌을 때, 각 리스트에서 최소한 하나의 원소를 포함하는 가장 작은 범위를 찾는 문제입니다.

입력 예시

nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]

출력 예시

[20,24]

문제 해결 아이디어

1. 접근 방법

슬라이딩 윈도우 + 우선순위 큐

• 각 리스트의 첫 번째 원소를 우선순위 큐에 저장
• 현재 큐에 있는 원소들의 최소값과 최대값을 이용해 범위 계산
• 최소값을 가진 리스트의 다음 원소를 큐에 추가하면서 범위 갱신

Input: [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
초기 상태: [4,0,5] -> range [0,5]
다음 상태: [4,9,5] -> range [4,9]
...
최종 결과: [20,24]

2. 구현 세부사항

알고리즘 동작과정

1. 초기화
   • 각 리스트의 첫 번째 원소를 우선순위 큐에 추가
   • 현재까지의 최대값(currentMax) 저장
   • 결과 범위의 시작(start)과 끝(end) 초기화
2. 반복 처리
   • 우선순위 큐에서 최소값을 가진 노드 추출
   • 현재 범위(currentMax - 최소값)가 이전 범위보다 작으면 갱신
   • 해당 리스트의 다음 원소를 큐에 추가 + 최대값 갱신
3. 종료 조건
   • 큐의 크기가 리스트의 개수와 같지 않으면 종료
   • 이는 어떤 리스트의 모든 원소를 다 사용했다는 의미

1. 초기 상태: pq=[0,4,5], currentMax=5
2. 0을 꺼내고 9 삽입: pq=[4,5,9], currentMax=9
3. 4를 꺼내고 10 삽입: pq=[5,9,10], currentMax=10
...

3. 시간 복잡도

• N: 모든 리스트의 전체 원소 수
• K: 리스트의 개수 (슬라이딩 윈도우 크기)
• 시간 복잡도: O(N * log K)
  • 각 원소는 한 번씩 우선순위 큐에 들어가고 나옴
  • 우선순위 큐의 삽입/삭제는 O(log K)

4. 구현

class Node {
    int n;            // 실제 숫자 값
    int listIndex;    // 리스트의 인덱스
    int elementIndex; // 리스트 내 원소의 인덱스
    
    public Node(int n, int listIndex, int elementIndex) {
        this.n = n;
        this.listIndex = listIndex;
        this.elementIndex = elementIndex;
    }
}

public int[] smallestRange(List<List<Integer>> nums) {
    // 우선순위 큐 초기화 - 최소값을 기준으로 정렬
    PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> o1.n - o2.n);
    
    int start = 0;
    int end = Integer.MAX_VALUE;
    int currentMax = Integer.MIN_VALUE;
    
    // 각 리스트의 첫 번째 원소를 큐에 추가
    for (int i = 0; i < nums.size(); i++) {
        priorityQueue.add(new Node(nums.get(i).get(0), i, 0));
        currentMax = Math.max(currentMax, nums.get(i).get(0));
    }
    
    // 메인 로직
    while (priorityQueue.size() == nums.size()) {
        Node cur = priorityQueue.poll();
        
        // 현재 범위가 이전 범위보다 작으면 갱신
        if (currentMax - cur.n < end - start) {
            start = cur.n;
            end = currentMax;
        }
        
        // 다음 원소가 있으면 큐에 추가
        if (cur.elementIndex + 1 < nums.get(cur.listIndex).size()) {
            int next = nums.get(cur.listIndex).get(cur.elementIndex + 1);
            priorityQueue.add(new Node(next, cur.listIndex, cur.elementIndex + 1));
            // 최대값 갱신
            currentMax = Math.max(currentMax, next);
        }
    }
    
    return new int[]{start, end};
}