문제 개요
배열 arr가 주어졌다고 가정해 봅시다. 우리는 정수들의 집합을 하나 선택한 뒤, 그 정수들이 배열에 등장하는 모든 항목을 한 번에 제거할 수 있습니다. 이때 목표는 배열 전체 원소의 절반 이상을 제거하기 위해 필요한 집합의 최소 크기를 구하는 것입니다.
예를 들어 arr = [3,3,3,3,5,5,5,2,2,7]인 경우를 살펴보겠습니다. 이때 출력값은 2입니다. 그 이유는 다음과 같습니다.
- {3, 7}을 선택하면 새 배열은 [5, 5, 5, 2, 2]가 되고, 크기는 5로 원래 배열 크기(10)의 절반과 같습니다.
- 크기가 2인 가능한 집합은 {3, 5}, {3, 2}, {5, 2} 등이 있습니다.
- 반면 {2, 7}을 선택하면 새 배열이 [3, 3, 3, 3, 5, 5, 5]가 되어 크기가 7로 원래 배열 크기의 절반보다 커지므로 조건을 만족하지 못합니다.
풀이 접근 방법
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '등장 빈도가 가장 높은 숫자부터 제거하면, 적은 수의 숫자만으로도 절반 이상을 지울 수 있다'는 것입니다.
구체적인 해결 단계는 다음과 같습니다.
- 맵(map) m을 정의하고, n := arr의 크기로 설정합니다. 각 원소의 등장 빈도를 맵 m에 저장합니다.
- 임시 배열 temp를 선언하고, sz := n, ret := 0으로 초기화합니다.
- 맵 m의 각 key-value 쌍(it)에 대해 value(빈도 값)를 temp에 삽입합니다.
- temp 배열을 내림차순으로 정렬합니다.
- i를 0부터 temp의 크기까지 반복하면서:
- sz <= n / 2이면 반복문을 종료합니다.
- ret을 1 증가시킵니다.
- sz에서 temp[i]만큼 감소시킵니다.
- ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSetSize(vector<int>& arr) {
unordered_map <int, int> m;
int n = arr.size();
for(int i = 0; i < n; i++){
m[arr[i]]++;
}
vector <int> temp;
unordered_map <int, int> :: iterator it = m.begin();
int sz = n;
int ret = 0;
while(it != m.end()){
temp.push_back(it->second);
it++;
}
sort(temp.rbegin(), temp.rend());
for(int i = 0; i < temp.size(); i++){
if(sz <= n / 2)break;
ret++;
sz -= temp[i];
}
return ret;
}
};
main(){
vector<int> v = {3,3,3,3,5,5,5,2,2,7};
Solution ob;
cout << (ob.minSetSize(v));
}입력
[3,3,3,3,5,5,5,2,2,7]
출력
2
코드 설명 및 시간 복잡도
위 코드는 먼저 unordered_map을 사용해 각 숫자의 등장 횟수를 계산합니다(O(n)). 이후 빈도 값들만 추출하여 내림차순으로 정렬한 뒤(O(k log k), k는 서로 다른 숫자의 개수), 가장 빈도가 높은 숫자부터 차례대로 제거하면서 남은 원소 수(sz)가 전체의 절반 이하가 될 때까지 진행합니다. 이렇게 하면 최소한의 숫자 종류만 제거해서 목표를 달성할 수 있으며, 시간 복잡도는 대략 O(n + k log k)입니다.