백준 2108번 - 통계학

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

2108번: 통계학

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

주어진 n개의 수들에 대하여 위의 4가지 값을 구하는 문제이다.

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    int x;
    cin >> n;
    int* a = new int[n];
    vector<int> v;
    for (int i = 0; i < n; i++) {
        cin >> x;
        a[i] = x;
    }
    double b = 0;
    for (int i = 0; i < n; i++) {
        b += a[i];
    }
    if (b < 0) {
        int c = int(-1 * (b / n) + 0.5) * -1;
        cout << c << '\n';  //음수 산술평균을 반올림
    }
    else {
        int c = int((b / n) + 0.5);
        cout << c << '\n';  //양수 산술평균을 반올림
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    cout << a[(n - 1) / 2] << '\n'; //위에서 오름차순으로 정렬한 값들중 중간값
    for (int i = 0; i < n - 1; i++) {
        int d = 1;
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j]) {
                d++;
            }
        }
        v.push_back(d);
    }  // 이중 for문으로 최빈값을 구하려고 시도했음
    v.push_back(1);
    int e = 0;
    int max_index = max_element(v.begin(), v.end()) - v.begin();
    for (int i = max_index + 1; i < n; i++) {
        if (v[i] == v[max_index]) {
            e++;
        }
    }
    if (e == 0) {
        cout << a[max_index] << '\n'; 
    }
    else {
        v[max_index] = 0;
        int max_index1 = max_element(v.begin(), v.end()) - v.begin();
        cout << a[max_index1] << '\n';
    }
    cout << a[n - 1] - a[0] << '\n'; // 정렬한 표에서 가장 큰값과 ㅏㄱ은값 
}

위의 코드처럼 하였더니 이중 for문에서 overflow가 발생하여 시간 초과가 나타났다. 

그래서 입력되는 정수 값들이 4000을 넘지 않는다는 점을 이용해 0부터 8000까지의 인덱스를 가지는 벡터1을 새로 만들어주고, 입력받은 숫자의 값 +4000 을 한 값이 몇번 등장하는지를 벡터 1의 각 인덱스의 값을 증가시킴으로써 기록해 주었다.

(예를 들자면 1을 입력 받을 경우 벡터 1의 4001번째 인덱스에 해당하는 값을 +1 해주어 횟수를 기록하는 방식이다.)

마지막에 최빈값에 해당하는 인덱스에서 4000을 뺀 값을 답으로 출력하면 된다. 최빈값이 여러개일 경우 벡터 1의 최빈값에 해당하는 인덱스를 0으로 만들어 주어 다시 최빈값을 찾는 방식으로 최빈값 중 두번째로 작은 수를 찾아낼 수 있었다.

아래는 수정한 코드이다.

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    int x;
    cin >> n;
    vector<int> a;
    vector<int> v;
    for (int i = 0; i < 8001; i++) {
        v.push_back(0);
    }
    for (int i = 0; i < n; i++) {
        cin >> x;
        a.push_back(x);
    }
    double b = 0;
    for (int i = 0; i < n; i++) {
        b += a[i];
    }
    if (b < 0) {
        int c = int(-1*(b / n) + 0.5)*-1;
        cout << c << '\n';
    }
    else {
        int c = int((b / n) + 0.5);
        cout << c << '\n';
    }
    sort(a.begin(), a.end());
    cout << a[(n-1) / 2]<<'\n';
    for (int i = 0; i < n; i++) {
        v[a[i]+4000]++;
    }
    int e = 0;
    int max_index = max_element(v.begin(), v.end()) - v.begin();
    for (int i = max_index+1; i < 8001; i++) {
        if (v[i] == v[max_index]) {
            e++;
        }
    }
    if (e == 0) {
        cout << max_index-4000 << '\n';
    }
    else {
        v[max_index] = 0;
        int max_index1 = max_element(v.begin(), v.end()) - v.begin();
        cout << max_index1-4000 << '\n';
    }
    cout << a[n - 1] - a[0] << '\n';
}