2108번 - 통계학 #구현

esc247·2022년 6월 30일
0

Algorithm

목록 보기
2/11

2108번


주어진 수 배열에 대해 네가지 값 구하는 문제.
쉽게 봤는데 생각보다 확인해야 할 부분이 많았다.
산술평균의 경우

  • 반올림할 때 cmath의 round() 함수를 사용
  • 평균 값이 음수가 됐을 때, int 인 수를 나누면 문제 생긴다
    ex) round(-9/5) 하면 -1 나오는데 이는 나눌때 소수부를 버리기 때문이다. 그래서 각각 float 나 double 로 캐스팅 변환 필요

중앙값은 N이 홀수라는 조건 있기에 간단.
범위 주어진 조건대로 역시 sort 후 배열의 처음과 끝 수의 차 구하면 된다.

최빈값이 가장 오래 걸렸다.
처음에는 이중 for문을 이용해 배열을 처음부터 같은 수가 있는지 확인하고 있으면 count++, 다 돌고 지금까지 구한 빈도의 최댓값과 같으면 벡터에 추가,
다 끝나면 벡터 정렬하고 문제에서 같은 빈도면 두번째로 작은 값을 출력하라고 했기에, 벡터의 size가 1보다 크면 vector[1] 출력,
그렇지 않으면 vector[0] 출력.

그런데 이렇게 푸니 시간초과 발생.
N이 500,000 까지여서 이중 for문 사용시 10^10이 되어서 그런 것 같다.

그래서 풀이를 참고하니,
음수 값이 있고 주어지는 숫자의 최댓값이 4000 이기에
인덱스로 카운트하는 배열을 만들고 그 크기를 8000으로 해서
음수의 경우 절댓값을 구한 후 4000을 더해서 그 인덱스에 저장하고, 인덱스에 해당하는 배열 값 ++.
그 후 max_element로 배열의 최댓값 구하고 최빈값 배열에 저장 후 최빈값 출력.

  • max_element(포인터,포인터) : 출력값도 포인터여서 *자료형에 저장해야한다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int arr[500001];
int freqarr[8001] = {
    0,
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int sum = 0;
    int avg, mid, freq, range = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }
    sort(arr, arr + n);
    avg = round(float(sum) / float(n));
    mid = arr[n / 2];
    if (n != 1)
        range = arr[n - 1] - arr[0];
    else
        range = 0;

    int freqcnt = 1;
    vector<int> freqvec;
    for (int i = 0; i < n; i++)
    {
        int temp = arr[i];
        if (temp < 0)
        {
            freqarr[abs(temp) + 4000]++;
        }
        else
        {
            freqarr[temp]++;
        }
        // for (int j = i + 1; j < n; j++)
        // {
        //     if (arr[i] == arr[j])
        //     {
        //         count++;
        //     }
        // }
        // if (freqcnt <= count)
        // {
        //     freqvec.push_back(temp);
        // }
    }
    int *m = max_element(freqarr, freqarr + 8000);
    for (int i = 0; i < 8001; i++)
    {
        if (freqarr[i] == 0)
            continue;
        if (freqarr[i] == *m)
        {
            if (i > 4000)
            {
                freqvec.push_back(-(i - 4000));
            }
            else
                freqvec.push_back(i);
        }
    }

    sort(freqvec.begin(), freqvec.end());
    if (freqvec.size() > 1)
        freq = freqvec[1];
    else
        freq = freqvec[0];
    cout
        << avg << '\n'
        << mid << '\n'
        << freq << '\n'
        << range << '\n';
    return 0;
}
profile
막상 하면 모르니까 일단 하자.

0개의 댓글