BOJ - 통계학(2108)

실버4 : 정렬

생각

최빈값 구할 때, 머리를 좀 써야한다. map구조를 잘 써볼 것. 그리고 정렬하는 방법도 고민해볼 것.

Code

//
//  main.cpp
//  test2
//
//  Created by 최완식 on 2021/03/29.
//
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N = 0;
int input[500001] = {0,};
int temp[500001] = {0,};
int a = 0;
int b = 0;
int c = 0;
int d = 0;
 
 
bool comp(const pair<int, int> &p1, const pair<int, int> &p2){
    if (p1.second == p2.second) {
        return p1.first < p2.first;
    }
    return p1.second > p2.second;
}
 
 
void merge(int left, int right){
    int mid = int((left+right)/2);
    int i = left, j = mid+1, k = left;
    
    while (i <= mid && j <= right) {
        if (input[i] <= input[j]) {
            temp[k] = input[i];
            i++;
        } else {
            temp[k] = input[j];
            j++;
        }
        k++;
    }
    
    int tmp = (i > mid) ? j : i;
    
    while(k <= right){
        temp[k] = input[tmp];
        k++;
        tmp++;
    }
    
    for (int i = left; i <= right; i++) {
        input[i] = temp[i];
    }
}
 
void partition(int left, int right){
    if (left >= right) {
        return;
    }
    int mid = int((left+right)/2);
    partition(left, mid);
    partition(mid+1, right);
    merge(left, right);
}
 
 
 
int main(){
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> input[i];
        a += input[i];
    }
    a = int(round(float(a)/N)); // 산술 평균
    
    partition(0, N-1); // 정렬
    
    b = input[int(N/2)]; // 중앙값
    
    // 최빈값
    vector<pair<int, int>> st;
    for (int i = 0; i < N; i++) {
        if (st.empty()) {
            st.push_back(pair<int, int>(input[i], 1));
            continue;
        }
        if (st.back().first == input[i]) {
            pair<int, int> tmp = st.back();
            tmp.second++;
            st.pop_back();
            st.push_back(tmp);
        } else {
            st.push_back(pair<int, int>(input[i], 1));
        }
    }
    sort(st.begin(), st.end(), comp);
 
    if (st[0].second == st[1].second) {
        c = st[1].first;
    } else {
        c = st[0].first;
    }
    
    // 범위
    d = input[N-1] - input[0];
    
    cout << a << '\n';
    cout << b << '\n';
    cout << c << '\n';
    cout << d << '\n';
 
    return 0;
}
 

Reference

• 백준(2108번) - 통계학