안녕? 적폐가 만연한 프갤의 부흥을 꿈꾸는 마음에서 프로그래밍글을 초보적이나마 써보려하는 유동이야. 잘부탁해!


Problem Link: https://www.careercup.com/question?id=16759664


Solution:

  간단하게, K개의 원소를 BBST(balanced BST)로 관리하면 된다(사실 Heap이나 Selection Tree를 써도 같은 복잡도를 얻을 수 있다). 

  다음과 같은 List들이 있다고 하자(즉 K=3):


 List 1: [ 4, 10, 15, 24, 26]

 List 2: [ 0,  9, 12, 20]

 List 3: [ 5, 18, 22, 30]


 우선 각 리스트에서 숫자를 하나씩 뽑는다.

 그리고 다시 이들을 BBST에 집어넣자(BBST: 삽입/삭제/검색 O(logN (*N=원소개수)), 최댓값/최솟값 쿼리 O(1)).

 [0, 4, 5] 처럼 될텐데, 이걸 보고 답을 [0, 5]로 갱신한다.

 이후에는 다음 작업을 반복해보자(*어느 리스트도 비어있지 않는 동안):

    1. 최솟값을 삭제한다.

    2. 해당 최솟값이 어느 리스트에서 나왔는지를 보고 해당 리스트의 다음 수를 가져온다.

        (이는 사실 BBST에 Key만 저장하지 말고 Key-Value Pair로 저장하여 [(0, 2), (4, 1), (5, 3)]처럼 관리하면 된다)

    3. 최댓값과 최솟값의 차이가 답보다 작으면 답을 갱신한다.


  N = 모든 리스트의 숫자의 개수의 합이라고 하면

  Additional Space Complexity는 O(K)

  Time Complexity는 O(NlogK)가 된다.


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
unsigned distance(int x, int y) {
  if (min(x, y) >= 0 || max(x, y) < 0) {
    return unsigned(max(x, y) - min(x, y));
  } else {
    unsigned ux = unsigned(max(x, y));
    unsigned uy = unsigned(-min(x, y));
    return max(ux, uy) + min(ux, uy);
  }
}
pair<int,int> get_smallest_common_range(const vector<vector<int>>& lists) {
  vector<vector<vector<int>>::size_type> ptr(lists.size());
  set<pair<int,vector<vector<int>>::size_type>> k_minimum;
  {
    vector<vector<int>>::size_type i = 0;
    for (const auto& p: ptr) {
      k_minimum.insert({lists[i][p], i});
      ++i;
    }
  }
  pair<int,int> answer = {k_minimum.begin()->first, k_minimum.rbegin()->first};
  while (++ptr[k_minimum.begin()->second] < lists[k_minimum.begin()->second].size()) {
    vector<vector<int>>::size_type i = k_minimum.begin()->second;
    k_minimum.erase(k_minimum.begin());
    k_minimum.insert({lists[i][ptr[i]], i});
    if (distance(k_minimum.begin()->first, k_minimum.rbegin()->first) < distance(answer.first, answer.second)) {
      answer = {k_minimum.begin()->first, k_minimum.rbegin()->first};
    }
  }
  return answer;
}
cs


연습문제1) Heap으로는 어떻게 바꾸면 될까요?

연습문제2) 정당성 증명(왜 이렇게 하면 답이 나올까요?)