[BOJ-2108][C++] 통계학

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	114349	24868	20070	25.402%

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

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

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

 

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

 

예제 입력 1

5
1
3
8
-2
2

 

예제 출력 1

2
2
1
10

 

예제 입력 2

1
4000

 

예제 출력 2

4000
4000
4000
0

 

예제 입력 3

5
-1
-2
-3
-1
-2

 

예제 출력 3

-2
-2
-1
2

 

예제 입력 4

3
0
0
-1

 

예제 출력 4 

0
0
0
1

(0 + 0 + (-1)) / 3 = -0.333333... 이고 이를 첫째 자리에서 반올림하면 0이다. -0으로 출력하면 안된다.

 

알고리즘 분류

• 수학
• 구현
• 정렬

 

문제 출처

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

2108번: 통계학

 

문제 해결 방법

• 정답률 25%의 어려운 문제이다.
• 문제에 주어진 여러 조건들을 생각하고 문제를 풀어야 했다.
  • 입력 받는 수(N)의 전체 개수는 홀수이다.
  • 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
  • 산술 평균은 소수점 이하 첫째 자리에서 반올림하여 출력한다.
    • -0으로 출력시키면 안된다.
  • 최빈값이 여러개 있을 경우, 최빈값 중 두 번째로 작은 값을 출력한다.
• 평균(Average), 중앙값(Median), 최빈값(Mode)은 통계학에서 대푯값(Representative Value)이라고 한다. (자세한 내용은 이곳 참고)
• 범위(Range)는 통계학에서 산포도(Measure of Dispersion) 중 하나이다. (자세한 내용은 이곳 참고)

 

문제 해결에 필요한 변수 선언

int N, num, sum, median, mode, cnt[8002], range, maxNum, minNum, maxCnt, flag;
double avg;
vector<int> nums, idxes;

 

N개의 숫자를 입력 받은 후 정렬시키기

for (int i = 0; i < N; i++) {
    cin >> num;
    nums.push_back(num);
    sum += num;    // 총합 계산하기
}

// 오름차순 정렬
sort(nums.begin(), nums.end());

• N개의 숫자를 입력 받은 후, 숫자가 담긴 벡터(nums)에 넣는다. 이와 동시에 입력 받은 숫자들의 총합(sum)을 업데이트 해준다.
• 입력을 모두 받은 후, 숫자가 담긴 벡터를 오름차순으로 정렬시킨다.

 

산술 평균 구하기

// (1) 산술 평균 구하기
avg = round((double)sum / N);    // 소수점 첫째 자리에서 반올림
avg = (int)avg;    // int 형으로 변환 (-0이 출력되지 않도록 하기 위함.)

• 평균 = 총합 / 개수 이다.
• 이 때 주의할 점은, 총합(sum) 변수를 double 형으로 명시적 형변환시켜야 한다는 것이다.
  • N 변수를 double 형으로 명시적 형변환시켜도 상관 없다.
  • 이것은 정확한 반올림이 수행되도록 하기 위함이다.
    • 예) 입력 받은 값들이 -1, -2, -3, -1, -2 일 경우 [예제 입력 3]
      • double 형으로 명시적 형변환을 하지 않는 경우
        • avg = round(-9 / 5) = round(-1) = -1
      • double 형으로 명시적 형변환을 하는 경우
        • avg = round(-9.0 / 5) = round(-1.8) = -2
      • 명시적 형변환의 사용 여부에 따라 결과값이 달라지게된다.
• 그리고 -0이 출력되지 않도록 하기 위해 double 형이었던 avg 변수를 int 형으로 변환시켜준다.
  • 부동 소수점형은 +0과 -0을 모두 표현할 수 있다. 따라서 -0을 출력시킬 수 있다.
    • 예) round(-0.5) => -0
  • 따라서 (+)0만 출력시키도록 하기 위해 int 형으로 변환시켜준다.

 

중앙값 구하기

// (2) 중앙값 구하기
median = nums[floor(N / 2)];  // 내림

• 벡터 nums는 오름차순으로 정렬되어 있다.
• 문제에서  N의 값은 홀수라는 조건이 있으므로, 중앙값은 배열의 중간의 인덱스에 있는 값이 된다.
• 예) 입력 받은 값들이 6, 2, 4, 8, 1인 경우
  • [1, 2, 4, 6, 8]  -> 중앙값은 4이며, 그 인덱스는 은 2(=floor(5 / 2))이다.

 

최빈값 구하기

// (3) 최빈값 구하기
for (int i = 0; i < N; i++) {
    cnt[nums[i] + 4000]++;
}

maxCnt = 0;
for (int i = 0; i < 8002; i++) {
    if (maxCnt < cnt[i]) {
        maxCnt = cnt[i];
    }
}

flag = 0;
for (int i = 0; i < 8002; i++) {
    if (cnt[i] == maxCnt) {
        flag++;
        idxes.push_back(i - 4000);
    }
}

mode = (flag >= 2) ? idxes[1] : idxes[0];

• 이 문제에서 제일 해결하기 어려웠던 부분이다.
• 문제의 조건에서 입력 받은 값들의 절댓값은 4000을 넘지 않는다고 하였다.
• 그래서 내부의 모든 요소가 0이고, 크기가 8000인 배열을 생성하여(cnt[8002]), 문제를 해결하는데 사용하였다.
• cnt 배열에서 가장 큰 수를 maxCnt 변수에 넣고, 다시 for 문을 돌려서 cnt 배열의 요소값과 maxCnt 변수의 값이 같을 경우, 최빈값의 수를 나타내는 변수(flag)의 값을 1씩 증가시키고 해당 숫자를 idxes 벡터에 넣도록 하였다.
  • idxes 벡터에는 최빈값들이 오름차순으로 쌓이게 된다.
• 반복이 끝난 후 flag의 값(최빈값의 수)이 2 이상일 경우, 문제의 조건에서 최빈값 중 두 번째로 작은 값을 출력하라고 되어 있으므로 idxes 벡터의 두 번째 요소(idxes[1])를 최빈값으로 설정한다. 그렇지 않을 경우 idxes 벡터의 첫 번째 요소(idxes[0])를 최빈값(mode)으로 할당한다.

 

범위 구하기

// (4) 최솟값, 최댓값, 범위 구하기
minNum = nums[0];
maxNum = nums[nums.size() - 1];
range = maxNum - minNum;

• nums 벡터를 오름차순으로 정렬한 상태이므로, nums 벡터의 첫 번째 요소 nums[0]에는 최솟값(minNum), 마지막 요소 nums[nums.size() -1]에는 최댓값(maxNum)이 된다.
• 최댓값 - 최솟값을 범위(range)로 할당한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int N, num, sum, median, mode, cnt[8002], range, maxNum, minNum, maxCnt, flag;
double avg;
vector<int> nums, idxes;

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

    cin >> N;    // N : 홀수

    for (int i = 0; i < N; i++) {
        cin >> num;
        nums.push_back(num);
        sum += num;    // 총합 계산하기
    }
    
    // 오름차순 정렬
    sort(nums.begin(), nums.end());

    // (1) 산술 평균 구하기
    avg = round((double)sum / N);    // 소수점 첫째 자리에서 반올림
    avg = (int)avg;    // int 형으로 변환 (-0이 출력되지 않도록 하기 위함.)

    // (2) 중앙값 구하기
    median = nums[floor(N / 2)];  // 내림
    
    // (3) 최빈값 구하기
    for (int i = 0; i < N; i++) {
        cnt[nums[i] + 4000]++;
    }

    maxCnt = 0;
    for (int i = 0; i < 8002; i++) {
        if (maxCnt < cnt[i]) {
            maxCnt = cnt[i];
        }
    }

    flag = 0;
    for (int i = 0; i < 8002; i++) {
        if (cnt[i] == maxCnt) {
            flag++;
            idxes.push_back(i - 4000);
        }
    }

    mode = (flag >= 2) ? idxes[1] : idxes[0];

    // (4) 최솟값, 최댓값, 범위 구하기
    minNum = nums[0];
    maxNum = nums[nums.size() - 1];
    range = maxNum - minNum;

    cout << avg << '\n' << median << '\n' << mode << '\n' << range << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [정렬]
• 실버III