수를 정렬하고 등장횟수를 저장한다.
수의 범위가 어느정도 한정적일 때에만 카운팅 소트를 사용할 수 있다.
ex 수의 범위가 10억이 넘는 경우 int로 잡아도 1.2억개의 수 만 저장 가능하고 이때 저장을 한다고 치면 512mb를 넘어가게 된다.
범위가 작을 떄 사용하면 굉장히 효율적인 코드가 나온다.
일의자리 , 십의 자리, 백의자리에 맞춰서 인덱스에 넣고 배열을 수행한다.
라딕스 소트에서 데이터를 넣는 저장공간은 배열이 아닌 동적리스트여야 한다.
배열의 공간이 정확히 얼마나 필요한지 알 수 없기 떄문에 크기를 무작정 크게 지정하게 된다면 공간낭비가 생기게 된다.
sort는 퀵소트 기반으로 생성되었다. O(NlgN)을 가지지만 최악의 경우 N^2의 정렬알고리즘을 갖는다. 또한 stable_sort가 아니기 때문에 (우선순위가 같을때 원소의 위치가 보장되어 있지 않다.) stable_sort가 필요한 상황에서는 sort대신 stable_sort를 사용하자 사용법은 sort와 같다.
#include <iostream>
#include <algorithm>;
#include <queue>;
#include <cstdlib>
#include <vector>
using namespace std;
/*
*[문제]
*준규가 가장 많이 가지고 있는 숫자를 적는다.
*
*[입력]
*1<= N <= 100000
* [IDEA]
* 정렬 한다.
* 수를 index로 사용하고 ++한다. 범위는 long long으로 한다.
*/
int main(void) {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n; cin >>n;
long long store[n];
for(int i=0; i<n; i++) {
cin >> store[i];
}
sort(store, store+n);
long long maxval =-(111<<62)-1;
int maxcnt=0;
int cnt=1;
for(int i=1; i<=n; i++) {
if(store[i] !=store[i-1]) {
if(cnt>maxcnt) {
maxcnt = cnt;
maxval = store[i-1];
}
cnt=1;
}else cnt++;
}
cout << maxval;
}