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

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

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Least Number of Unique Integers after K Removals

문제 유형 : 그리디, 해시, 정렬, 우선순위큐

문제 난이도 : Medium

 

문제

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

 

정수 배열 arr이가 주어진다. k개의 요소를 제거하고 난뒤의 중복되지 않는 정수의 최소 개수를 구하시오.

 

풀이

해시맵을 이용하여 숫자-개수의 꼴로 저장시킨다.

두 가지 풀이가 있는다:

 

1. 우선순위 큐 이용

우선순위 큐에 숫자-개수 쌍을 넣는다. 비교함수로 개수 기준의 최소 힙을 만든다.

우선순위 큐에서 요소를 꺼내면서 수를 지우는 방식으로 한다.

 

2. 정렬 이용

배열을 개수를 기준으로 정렬한 뒤, 인덱스 k이후부터 부분배열을 만들어서 중복 요소를 제거한 배열의 크기를 구하면 된다.

 

코드

C++ - 우선순위 큐 이용

struct comp {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
        return a.second > b.second;
    }
};

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> mp;

        for(const auto &num : arr) {
            mp[num]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;

        for(const auto &element : mp) {
            pq.push(make_pair(element.first, element.second));
        }

        int ans = mp.size();
        while(!pq.empty() && k > 0) {
            k -= pq.top().second;
            if(k >= 0) ans--;
            pq.pop();
        }

        return ans;
    }
};

Go - 정렬 이용

var mp map[int]int

type ByFreq []int

func (a ByFreq) Len() int           { return len(a) }
func (a ByFreq) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByFreq) Less(i, j int) bool {
    if mp[a[i]] == mp[a[j]] {
        return a[i] < a[j]
    }
    return mp[a[i]] < mp[a[j]]
}

func unique(arr []int) []int {
	encountered := map[int]bool{}
	res := []int{}

	for _, v := range arr {
		if !encountered[v] {
			encountered[v] = true
			res = append(res, v)
		}
	}
	return res
}

func findLeastNumOfUniqueInts(arr []int, k int) int {
	mp = make(map[int]int)

	for _, v := range arr {
		mp[v]++
	}
	sort.Sort(ByFreq(arr))
	arr = unique(arr[k:])

	return len(arr)
}