문제
10개의 자연수(10의 배수, 1000 이하)가 주어질 때, 평균과 최빈값을 구하라.
입력
10줄에 걸쳐 자연수가 하나씩 주어진다.
출력
첫째 줄에 평균, 둘째 줄에 최빈값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
10 40 30 60 30 20 60 30 40 10 | 33 30 |
풀이
합계로 평균을 구하고, 빈도 배열로 최빈값을 구한다.
- 10개의 수를 입력받으며 합계를 누적하고 빈도 배열에 등장 횟수를 기록한다
- 합계 / 10으로 평균을 구한다
- 빈도 배열에서 가장 높은 빈도를 가진 수를 최빈값으로 선택한다
핵심 아이디어: 값의 범위가 1000 이하로 작으므로 크기 1001의 빈도 배열로 O(1) 공간에 최빈값을 구할 수 있다.
코드
#include <iostream>
using namespace std;
int main()
{
int a[10];
int b[1001]{0};
int sum = 0;
for (int i = 0; i < 10; i++)
{
cin >> a[i];
sum += a[i];
b[a[i]]++;
}
int max = 0;
int num = 0;
for (int i = 0; i <= 1000; i++)
{
if (b[i] > max)
{
max = b[i];
num = i;
}
}
cout << sum / 10 << "\n";
cout << num;
}복잡도
- 시간: O(1) (고정 크기 10 + 1000)
- 공간: O(1)