이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 69 번째 글 입니다.
목차
실버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;
}