[Hello 2025] B. Gorilla and the Exam

문제 이해

중복 가능한 정수가 나열된 길이가 N인 수열이 있을 때, 해당 수열에서 범위 l, r을 잡아서 그 범위 안에서 가장 작은 수를 전부 삭제할 수 있을 때, 최소 몇 번의 삭제 연산이 필요한지 계산하는 문제이다.

여기서 중요한 것은 N과 함께 입력되는 K라는 입력값인데, 이 K값만큼 원하는 수들을 원하는 수로 변경시킬 수 있다.

예를 들어 K = 1인 경우, [1 2 1]이라는 배열을 [1 1 1]로 변화시켜 1번의 삭제 연산으로 배열의 수를 전부 삭제할 수 있는 것이다.

 

문제 해설

이 문제에서 주의할 점은 배열 안의 수가 배열된 순서가 큰 의미가 없다는 것이다.

결국에는 모든 수를 삭제하려면 최소한남아있는 수의 종류만큼 삭제 연산이 필요하기 때문이다.

즉, K를 이용하여 남아있는 수의 종류를 최소화하는게 이 문제의 포인트이다.

그러기 위해서는 입력 받은 수의 종류별로 개수를 카운팅 한 뒤에, 가장 개수가 작은 종류의 수부터 K의 범위 안에서 지우면 된다.

예를 들어, [1 2 2 3 3 3 4 4 4 4]라는 배열이 있고, K가 4라면 1, 2, 2를 지우는 것(다른 종류의 수로 바꾸는 것)이 연산 횟수를 줄이는 최선일 것이다.

이 행위를 코드로 구현하면 정답이다.

이 때 주의할 점은, 정수의 개수를 카운팅 시에 int배열이 아닌 Map을 이용해야 메모리 초과를 피할 수 있다는 점이다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>

using namespace std;

int T, N, K;

int main()
{
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d", &N, &K);
		map<int, int> mp;
		vector<int> v, temp;
		for (int i = 0; i < N; i++)
		{
			int inp;
			scanf("%d", &inp);
			v.push_back(inp);
		}
		for (int i = 0; i < N; i++)
		{
			mp[v[i]]++;
		}
		for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++)
		{
			temp.push_back(it->second);
		}
		sort(temp.begin(), temp.end(), greater<int>());
		while (!temp.empty())
		{
			int size = temp.back();
			if (size > K)
			{
				break;
			}
			else
			{
				K -= size;
				temp.pop_back();
			}
		}
		printf("%lu\n", (size_t)max((size_t)1, temp.size()));
	}

	return 0;
}