[C++] 백준 2108번 통계학

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

풀이 1

입력받은 정수를 벡터에 저장하고, 오름차순 정렬한 후

• 모두 더한 합계를 N으로 나누고 반올림하여 산술평균을 구한다.
• N/2 번째 수로 중앙값을 구한다.
• 벡터의 첫번째 수와 마지막 수의 차를 구하여 범위를 구한다.
• 중복되는 값의 개수를 다른 벡터에 저장하여 최빈값을 구한다.

코드 1

초기 버전

최빈값을 구할 때, 정렬된 정수 벡터에서 어떠한 수가 처음 등장하는 인덱스를 구하고,
새로운 카운팅 벡터의 해당 인덱스에 그 수가 등장하는 빈도를 저장한다.

카운팅 벡터의 뒤부터 순회하면서 현재 시점에서의 최대 빈도를 갖는 인덱스를 m에 저장하는데,
만약 기존 최대 빈도와 현재 빈도가 같다면 바로 직전에 최대 빈도를 갖는 인덱스를 p에 저장한다.
이 방식을 이용해 최빈값이 여러 개일 때 두번째로 작은 값을 출력한다.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    cin >> N;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    sort(v.begin(), v.end());

    int average = 0, median = 0, mode = 0, range = 0;
    int sum = 0, max = 0;

    vector<int> cnt(N);
    for(int i=0; i<N; i++) {
        sum += v[i];

        if(i == N/2) median = v[i];

        if(v[max] < v[i]) {
            max = i;
            cnt[max]++;
        }
        else if(v[max] == v[i]) {
            cnt[max]++;
        }
    }

    int m = N-1, p = 0;
    for(int i=N-1; i>=0; i--) {
        if(cnt[m] < cnt[i]) {
            m = i;
            p = 0;
        }
        else if(cnt[m] == cnt[i]) {
            p = m;
            m = i;
        }
    }

    mode = (p == 0) ? v[m] : v[p];
    range = v[N-1] - v[0];
    average = round((double)sum / N);

    cout << average << "\n" << median << "\n" << mode << "\n" << range;
    
    return 0;
}

수정 버전

정렬된 정수 벡터를 선회하면서 새로운 빈도 벡터에 현재 시점에서의 최빈값을 모두 저장한다.
만약 기존 최빈값의 빈도보다 큰 빈도를 가지는 정수가 등장했을 때, 이를 새로운 최빈값으로 정의하고 빈도 벡터를 초기화하여 같은 빈도의 최빈값들만 저장할 수 있도록 한다.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    cin >> N;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    sort(v.begin(), v.end());

    int sum = 0;
    for(int x : v) sum += x;
    int average = round(sum / (double)N);

    int median = v[N/2];
    int range = v.back() - v.front();

    int maxFreq = 0;
    vector<int> f;
    int i = 0;
    while(i < N) {
        int j = i + 1;
        while(j < N && v[j] == v[i]) j++;

        int freq = j - i;
        if(freq > maxFreq) {
            maxFreq = freq;
            f.clear();
            f.push_back(v[i]);
        } else if(freq == maxFreq) {
            f.push_back(v[i]);
        }

        i = j;
    }

    int mode = (f.size() == 1) ? f[0] : f[1];

    cout << average << "\n" << median << "\n" << mode << "\n" << range;
    
    return 0;
}

풀이 2

counting sort 방법

입력되는 정수의 절댓값은 4000을 넘지 않으므로 최소 -4000, 최대 4000이다.
크기가 8001인 카운팅 벡터를 생성하고 입력되는 정수의 빈도를 저장한다.