[👍][PriorityQueue][Easy] 703. Kth Largest Element in a Stream

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

정수형 입력 데이터가 주어질 때, k 번째로 큰 값을 반환하도록 하라.

 

조금 함정이 있는 문제다. 

데이터가 얼마나 있는지, 다른 데이터는 무엇인지, 사실 문제는 관심없다. 

오로지 반환으로 원하는 것은 k 번째 큰 값이다. 

 

우선 map 등의 정렬된 hash등으로 값을 가질 수 있다.

모든 값이 보존되며, add 시 정렬로 인해, O(logN) 시간이 소요 된다. 

하지만 검색 시도 O(logN)이 소요된다. 

( O(1) 을 원하면 hash_map 을 써야 하지만, 정렬이 지원되지 않는다. )

이것으로도 충분히 문제는 풀릴 것이다. 

 

다음으로 priority queue를 생각해 볼 수 있다. 

TC관점에서 add, pop 모두 O(logN)으로 같지만, 값 반환 시간은 O(1)이다. (최대나 최소값만 반환하므로)

 

따라서 특정 값에 삽입/삭제를 최소화 하고 접근만 빈번할 때, priory queue가 언제나 map 보다는 낫다. 

하지만, 어떻게 k 번째 큰 값을 찾도록 queue를 구성하는가. 

 

우선 minQueue를 구성하고 모든 data를 넣는다. 

크기가 k 가 되도록 데이터를 pop한다. 

그러면 결과적으로 가장 큰 녀석들 중, 제일 작은 녀석만 접근 가능한 상태로 minQueue가 구성된다. 

그리고 이 제일 작은 접근 가능한 값이 k 번째로 큰 값이다. 

 

이 상태에서 값을 add하면, 

minQueue의 front 보다 작으면 무시한다. 

크다면 minQueue에 push하고 다시 size()가 k 가 될때까지 pop한다.(이미 처리 했으므로 보통 여기서는 1회만 하면 됨)

-> 따라서 다시 minQueue는 k개의 가장 큰 값들 중 제일 작은 녀석을 top으로 하고, 이것이 k 번째 큰 값이 된다. 

( 다른 값은 잃거나 얻지 못하게 될 것이지만, 이는 문제가 요구하는 것이 아니므로, 괜찮다. )

 

code 

class KthLargest {
    priority_queue<int, std::vector<int>, std::greater<int> > mMinPQueue;
	int mK;
    
public:

    KthLargest(int k, vector<int>& nums)
    {
        mK = k;
        for (int q = 0; q < nums.size(); ++q)
            mMinPQueue.push(nums[q]);

        while (mMinPQueue.size() > mK)
            mMinPQueue.pop();
    }
    int add(int val)
    {
        if (mMinPQueue.size()<mK || val>=mMinPQueue.top())
        {
            mMinPQueue.push(val);

            while (mMinPQueue.size() > mK)
                mMinPQueue.pop();
        }
        return mMinPQueue.top();
    }
};

 

 

result

 

Note 1) map을 썼을 때 보다, 성능은 낫다. 

Note 2) 이 문제가 easy 난이도 라는 것은, priroty queue를 이런 식으로 응용해서 많이 쓴다는 것이다. 잘 이해해 두자.