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

걸린 시간: 35m38s

문제

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

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

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

문제 접근 방법

• 산술평균의 경우는 입력을 받을 때 값을 계속해서 더해주고 마지막에 N으로 나눠주면 된다. 이 때 주의할 점을 float이 아니라 double을 사용할 것.
• 중앙값과 범위의 경우는 vector<int>를 사용해서 값을 저장했고 이를 정렬한 후 쉽게 구할 수 있었다.
• 문제는 최빈값인데, 단순히 가장 많이 나타난 값을 구하는 것을 쉬운데 여러개 있을 때 두 번째로 작은 값을 출력하란다.. 설명은 코드로 대신한다..

1// mymap<값, 등장 횟수>
2auto it = mymap.begin();
3map<int, vector<int> > mode;
4while(it != mymap.end()) {
5    auto m = mode.find(it->second);
6    if(m == mode.end()) {
7        vector<int> temp;
8        temp.push_back(it->first);
9        mode.insert(make_pair(it->second, temp));
10    } else {
11        (m->second).push_back(it->first);
12    }
13    ++it;
14}
15
16auto modev = (mode.rbegin())->second;
17int mode2 = (modev.size() > 1) ? modev[1] : modev[0];

C++ 코드

1#include <bits/stdc++.h> 
2using namespace std; 
3#define ios cin.tie(NULL), ios_base::sync_with_stdio(false)
4#define endl '\n'
5
6int main() {
7  int n;
8  double sum = 0.0f;
9  map<int,int> mymap;
10  vector<int> v;
11
12  cin >> n;
13  for(int i=0; i<n; ++i) {
14    int t; scanf("%d", &t);
15    sum += (double)t;
16    v.push_back(t);
17    (mymap[t])++;
18  }
19
20  sort(v.begin(), v.end());
21
22  auto it = mymap.begin();
23  map<int, vector<int> > mode;
24  while(it != mymap.end()) {
25    auto m = mode.find(it->second);
26    if(m == mode.end()) {
27      vector<int> temp;
28      temp.push_back(it->first);
29      mode.insert(make_pair(it->second, temp));
30    } else {
31      (m->second).push_back(it->first);
32    }
33    ++it;
34  }
35
36  auto modev = (mode.rbegin())->second;
37  int mode2 = (modev.size() > 1) ? modev[1] : modev[0];
38
39  sum = (sum/n);
40  sum = sum + ((sum > 0) ? 0.5 : -0.5); 
41  printf("%d\n", (int)(sum));
42  printf("%d\n%d\n%d\n", v[v.size()/2], mode2, v[v.size()-1]-v[0]);
43
44  return 0;
45}

시간 복잡도

• N개의 숫자 입력 vector - O(N)
• N개의 숫자 입력 map - O(N logK), K = map size
• sort() - O(NlogN)
• 최종 시간 복잡도: O(N) + O(N logK) + O(N logN)

공간 복잡도

• 숫자 카드 N개를 저장 vector - O(N)
• 숫자 카드 N개를 저장 map - O(2N)
• 최종 공간 복잡도: O(N) + O(2N) => O(N)