[Leetcode] 703. Kth Largest Element in a Stream 문제 풀이

https://leetcode.com/problems/kth-largest-element-in-a-stream/

Kth Largest Element in a Stream - LeetCode

문제 내용

데이터가 계속 추가되는 상황에서 k번째 큰 수를 return 하는 문제

 

Example 1:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

문제 풀이

1. 삽입 정렬과 바이너리 서치 사용

데이터 하나가 들어올 때 정렬된 상태를 유지 하기 위해 삽입 정렬을 사용했다.

그리고 어디에 삽입할 지 찾는 부분은 그냥 하면 O(n) 걸리기 때문에

정렬된 데이터에서 빠르게 찾기 위해 바이너리 서치를 사용했다.

그리고 return 할때는 O(1) 만에 할 수 있다.

 

2. Min heap 사용

여기서 알아야할 것은 k번째 데이터만 알면 된다.

그래서 모든 데이터를 정렬된 상태로 유지할 필요가 없다.

가장 큰 데이터 순서대로 k번째까지만 있으면 가장 작은 값이 k번째 큰 수가 된다.

min heap 크기를 k까지만 유지하도록 했다.

 

코드

1. 삽입 정렬과 바이너리 서치

class KthLargest {
public:
    vector<int> container;
    int k;
    
    KthLargest(int k, vector<int>& nums) : k(k-1) {
        for_each(nums.begin(), nums.end(), [&] (const int& num) { insert(num); });
    }
    
    int add(int val) {
        insert(val);
        return container[k];
    }
    
    void insert(int num) {
        auto it = lower_bound(container.begin(), container.end(), num, [] (int num, int target) {
            return num > target;
        });
        if (it - container.begin() <= k)
            container.insert(it, num);
    }
};

2. min heap 사용

class KthLargest {
public:
    int k;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    
    KthLargest(int k, vector<int>& nums) : k(k-1) {
        sort(nums.begin(), nums.end(), greater<int>());
        int size = min((int)nums.size(), k);
        for (int i = 0; i < size; ++i) {
            min_heap.push(nums[i]);
        }
    }
    
    int add(int val) {
        insert(val);
        return min_heap.top();
    }
    
    void insert(int num) {
        if (min_heap.empty() || min_heap.size() <= k) {
            min_heap.push(num);
        }
        else if (num > min_heap.top()) {
            min_heap.push(num);
            min_heap.pop();
        }
    }
};