[LeetCode] 1481. Least Number of Unique Integers after K Removals

https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/

Least Number of Unique Integers after K Removals - LeetCode

Least Number of Unique Integers after K Removals - Medium

 

배열에서 k개의 숫자를 지웠을때 남아있는 수에서 각각의 숫자의 개수 중 최소값을 출력하는 문제다.

hash map을 이용해 각각의 숫자의 개수를 저장하고,

priority queue를 이용해 k개 만큼 지워주자.

 

전체 풀이 코드

class Solution {
public:
    struct compare{bool operator()(pair<int,int> a, pair<int,int> b) {return a.second>b.second;}};
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> m;
        priority_queue<pair<int,int>, vector<pair<int,int>>, compare> pq;
        int N=0, ret=0;
        for (int n:arr) {
            if (m.find(n)==m.end()) m[n]=0,N++;
            m[n]++;
        }
        for (auto n:m) pq.push(make_pair(n.first,n.second));
        while(k) {
            pair<int, int> p = pq.top();
            if (k>=p.second) k-=p.second, pq.pop();
            else break;
        }
        return pq.size();
    }
    
};