1335-C, *1100

Problem - 1335C - Codeforces

문제

• $n(1 \leq n \leq 2 \cdot 10^{5})$개의 수 중 일부를 사용하여
  크기가 같은 두 개의 집합 $A,\ B$을 구성한다, $\left | A \right | = \left | B \right |$
• $A$에는 같은 수가 들어가면 안된다
• $B$에는 같은 수만 들어가야 한다
• $\left | A \right | = \left | B \right |$를 최대로 구성할 때 집합의 크기는?
• $O(nlog\ n)$ 정도의 알고리즘은 통과할 수 있다

 

$O(nlog\ n)$

수의 개수를 세서 map에 보관하자 $O(nlog\ n)$

값	3	5	7	8
개수	1	2	3	4 $=\mathrm{maxval}$

i) $\mathrm{map.size}<\mathrm{maxval}$ ~ $\mathrm{map.size}$
ii) $\mathrm{map.size}=\mathrm{maxval}$ ~ $\mathrm{map.size-1}$
iii) $\mathrm{map.size}>\mathrm{maxval}$ ~ $\mathrm{maxval}$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        map<int, int> m;
        m.clear();
        int tmp;
 
        while(n--){
            cin >> tmp;
            m[tmp]++;
        }
 
        int max_num = 0;
        for(auto e: m) max_num = max(max_num, e.second);
 
        if(m.size() < max_num) cout << m.size() << endl;
        else if(m.size() == max_num) cout << m.size()-1 << endl;
        else cout << max_num << endl;
 
    }
 
 
    return 0;
}cs