[Silver V] 마트료시카 합치기 - 25631

[문제 위치]

https://www.acmicpc.net/problem/25631

[문제 풀이]

마트료시카의 크기들을 오름차순으로 정렬하면 문제를 단순화할 수 있다.

작은 크기부터 그룹화하며 최대한 많은 마트료시카를 합치는 것이 핵심이다.
이 과정에서 크기가 같은 마트료시카는 독립적으로 처리해야 하므로, 가장 많이 등장한 크기의 개수가 최소 그룹의 수를 결정한다.

정렬과 간단한 빈도 계산으로 효율적으로 해결할 수 있으며, 불필요하게 복잡하게 접근할 필요가 없다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int getMinMatryoshkaCount(int n, vector<int>& sizes) {
    sort(sizes.begin(), sizes.end());
    unordered_map<int, int> frequency;
    for (int size : sizes) {
        frequency[size]++;
    }
    int maxFrequency = 0;
    for (auto& [size, count] : frequency) {
        maxFrequency = max(maxFrequency, count);
    }
    return maxFrequency;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> sizes(n);
    for (int i = 0; i < n; i++) {
        cin >> sizes[i];
    }
    cout << getMinMatryoshkaCount(n, sizes) << '\n';
    return 0;
}