백준 02108 - 통계학

출처 : https://www.acmicpc.net/problem/2108 

2108번: 통계학

 

고려사항

• 머지소트로 구현을 해보았음. ( sort( ) 쓰면 편하지만 연습해보자구여~ )
•  같은 수가 배열에 포함 될 수 있으니 23 번 줄처럼 부등호로 비교를 하여 i 인덱스를 먼저 소모시켜준다.
  ( i 는 left 부터 시작했으니 더 빠른 인덱스이며, 머지 소트는 같은 값에 대하여 순서를 보장해주는 stable sort를 만족해야 한다. )
  (사실 이 문제에서 구현 안해도 큰상관은...ㅎ)
• 반올림은 cmath의 round 함수 활용.
• 최빈값은 -4000 ~ 4000 까지의 수가 들어올 수 있으니, num 이 vector에 인덱스가 될 수 있도록
  bias(4000) 값을 정한 후 더해주어 v[num] 에 넣어 주며,
  이 때, 원소는 pair<등장한 횟수, num> 이 된다.
• 벡터에 다 담았으면 cmp 함수 ( 7 - 13 라인 ) 를 만들어 sort 알고리즘을 활용하여 정렬.
  => 정렬하면 등장한 횟수를 기준으로 내림차순으로 정렬되고, 등장한 횟수가 같을 시엔 num 이 작은 페어가 앞으로 오게 한다.
  => v[0].first 와 v[1].first를 비교하여 같다면 v[1].second를, 아니면 v[0].second 를 출력한다.
  ( v(8001, {0,0}) 으로 초기화를 해주었기 때문에, 입력 받은 수가 1개일 때도 v[0].first 는 1, v[1].first 는 0으로 비교가 가능하다! )

 

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
 
bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.first == b.first){
        return a.second < b.second;
    }
 
    return a.first > b.first;
}
 
int externalArr[500001];
 
void merge(int arr[], int left, int mid, int right){
    int i = left;
    int j = mid+1;
    int idx = left;
 
    while(i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            externalArr[idx++] = arr[i++];
        }else{
            externalArr[idx++] = arr[j++];
        }
    }
 
    if(i > mid){
        while(j <= right){
            externalArr[idx++] = arr[j++];
        }
    }else{
        while(i <= mid){
            externalArr[idx++] = arr[i++];
        }
    }
 
    idx = left;
    while(idx <= right){
        arr[idx] = externalArr[idx];
        ++idx;
    }
}
 
void mergeSort(int arr[], int left, int right){
    if(left < right){
        int mid = (left + right) / 2;
 
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int n, tmp, maxNum, bias = 4000;
    int arr[500001];
    double sum = 0;
    vector<pair<int, int>> v(8001, {0,0});
 
    cin>>n;
    for(int i=1;i<=n;++i){
        cin >> tmp;
        arr[i] = tmp;
        sum += tmp;
        v[tmp+bias] = {v[tmp+bias].first+1, tmp};
    }
 
    mergeSort(arr, 1, n);
    sort(v.begin(), v.end(), cmp);
 
    cout<<round(sum/n)<<"\n";
    cout<<arr[(1 + n) / 2]<<"\n";
    if(v[0].first == v[1].first){
        cout<<v[1].second<<"\n";
    }else{
        cout<<v[0].second<<"\n";
    }
    cout<<arr[n] - arr[1]<<"\n";
 
    return 0;
}