Written by JS970
on February 3, 2023

2108 - 통계학

난이도: 실버 3
날짜: 2023년 2월 3일
상태: Correct
추가 검토 여부: No

solution

N개의 입력 정수에 대해 산술평균, 중앙값, 최빈값, 범위를 구하는 문제이다.
입력과 동시에 sum을 계산하여 산술평균을 구할 수 있다.
마찬가지로 입력과 동시에 입력의 최댓값 및 최솟값을 구하여 범위를 바로 구할 수 있다.
priority_queue를 minheap으로 구현하여 증가하는 순서대로 정렬한다. 이후 N/2번만큼 pop연산을 통해 중강값을 구할 수 있다.
최빈값을 구하기 위해서 -4000 ~ 4000의 정수를 나타내는 배열인 arr[8001]을 선언하였다. 각 배열은 index + 4000에 해당하는 정수값이 몇 번 입력되었는지를 저장한다.
문제 조건에서 최빈값이 여러 개일 경우에는 두 번째로 작은 값을 출력하여야 한다고 했으므로 이를 쉽게 탐색하기 위해 priority_queue를 이용한다.
priority_queue를 사용하여 arr배열에서 가장 큰 값을 가지는 index를 탐색한다.
위의 priority_queue에서 가장 큰 값을 pop한 이후에도 이 다음 priority_queue의 top이 이전 값과 같다면 최빈값이 여러 개 있는 경우이므로 이들 중 두 번째로 작은 값을 찾기 위해 priority_queue를 하나 더 선언한다.
pop을 사용하여 두 번째로 작은 priority_queue의 원소를 탐색한다.

code

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int * data = new int[N];
    int sum = 0;
    int max = -4001;
    int min = 4001;
    priority_queue<int, vector<int>, greater<int>> pq;
    int arr[8001] = {0, };
    for(int i = 0; i < N; i++)
    {
        scanf("%d", &data[i]);
        sum += data[i];
        pq.push(data[i]);
        arr[data[i]+4000]++;
        max = (data[i] > max) ? data[i] : max;
        min = (data[i] < min) ? data[i] : min;
    }

    double mean = floor(((double)sum / (double)N) + 0.5);
    cout << (int)mean << endl;

    for(int i = 0; i < N/2; i++) pq.pop();
    cout << pq.top() << endl;

    priority_queue<int> pq2;
    for(int i = 0; i < 8001; i++)
        pq2.push(arr[i]);
    if(pq2.top() == 0) pq2.pop();
    int fv = pq2.top();
    pq2.pop();
    if(pq2.top() == fv)
    {
        priority_queue<int, vector<int>, greater<int>> pq3;
        for(int i = 0; i < 8001; i++)
        {
            if(arr[i] == fv)
                pq3.push(i);
        }
        pq3.pop();
        cout << pq3.top() - 4000 << endl;
    }
    else
    {
        int idx;
        for(int i = 0; i < 8001; i++)
            if(arr[i] == fv)
                idx = i;
        cout << idx - 4000 << endl;
    }

    cout << max - min << endl;

    return 0;
}

ref

2108번: 통계학

Top