백준 2108: 통계학
/ 8분 분량 / 문제 풀이
Silver II 난이도 문제를 C++로 풀이한 내용입니다. 주어진 숫자들의 산술평균, 중앙값, 최빈값, 범위를 계산하는 문제입니다.
백준 2108: 통계학
Silver II 난이도 문제를 C++로 풀이한 내용입니다. 주어진 숫자들의 산술평균, 중앙값, 최빈값, 범위를 계산하는 문제입니다.
문제 소개
주어진 N개의 수들에 대해 다음 네 가지를 계산하는 문제입니다.
- 산술평균: N개의 수들의 합을 N으로 나눈 값으로, 소수점 첫째 자리에서 반올림합니다.
- 중앙값: N개의 수를 오름차순으로 정렬했을 때 가운데에 위치하는 값입니다.
- 최빈값: N개의 수들 중 가장 많이 나타나는 값입니다. 여러 개일 경우 두 번째로 작은 값을 출력합니다.
- 범위: N개의 수들 중 최댓값과 최솟값의 차이입니다.
접근 방법
문제에서 요구하는 네 가지 통계값을 계산해야 합니다. 각 통계값을 구하기 위해 적절한 자료구조와 알고리즘을 사용해야 합니다.
- 산술평균: 모든 수의 합을 구하고 N으로 나눈 후 반올림해야 합니다.
double형으로 나누고round()함수를 사용하면 됩니다. - 중앙값: 중앙값을 구하기 위해서는 수들을 정렬해야 합니다. 정렬된 배열에서 N이 홀수일 경우
arr[n/2]가 중앙값이 됩니다. - 최빈값: 최빈값을 구하기 위해 각 숫자의 빈도를 세어야 합니다.
map자료구조를 사용하면 숫자를 key로, 빈도를 value로 저장하여 효율적으로 관리할 수 있습니다.map은 자동으로 key를 오름차순으로 정렬해주므로, 최빈값이 여러 개일 경우 두 번째로 작은 값을 쉽게 찾을 수 있습니다. - 범위: 수들을 정렬하면 최댓값과 최솟값을 쉽게 알 수 있습니다. 정렬된 배열의 마지막 요소에서 첫 번째 요소를 빼면 범위가 됩니다.
풀이 과정
- 입력 받기: 먼저 입력받을 숫자의 개수
n을 읽어옵니다. - 데이터 저장 및 합계 계산:
n개의 숫자들을vector에 저장하면서 동시에 합계를 계산합니다. - 산술평균 계산: 계산된 합계를
n으로 나누고round()함수를 이용해 반올림한 후 출력합니다. - 중앙값 계산:
vector를sort()함수를 이용해 오름차순으로 정렬합니다. 정렬된vector에서arr[n/2]를 중앙값으로 출력합니다. - 최빈값 계산:
map<int, int> freq를 선언하여 각 숫자의 빈도를 저장합니다.- 입력된 숫자들을 순회하며
map에 각 숫자의 빈도를 증가시킵니다. map을 순회하며 가장 높은 빈도(maxFreq)를 찾습니다.- 다시
map을 순회하며maxFreq와 같은 빈도를 가진 숫자들을vector<int> modes에 저장합니다. modes벡터의 크기가 1보다 크면modes[1](두 번째로 작은 최빈값)을, 그렇지 않으면modes[0](유일한 최빈값)을 출력합니다.
- 범위 계산: 정렬된
vector의 마지막 요소(arr[n-1])에서 첫 번째 요소(arr[0])를 뺀 값을 범위로 출력합니다.
코드 설명
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
int main() {
// 입출력 속도 향상
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// 입력 개수 n 받기
int n;
cin >> n;
// 수들을 저장할 배열과 합 계산용 변수
vector<int> arr(n);
int sum = 0;
// 모든 수 입력받기
for (int i = 0; i < n; i++) {
cin >> arr[i];
sum += arr[i]; // 합계 계산
}
// 1. 산술평균 (반올림)
// sum을 n으로 나누면 평균이 나옴
// round()는 소수점 첫째 자리에서 반올림 (예: 3.5 → 4)
int mean = round((double)sum / n);
cout << mean << "\n";
// 2. 중앙값
// 중앙값을 구하려면 먼저 정렬해야 함
sort(arr.begin(), arr.end());
// n이 홀수이므로 arr[n/2]가 중앙값 (예: n=5일 때 0 1 "arr[2]" 3 4가 중앙)
int median = arr[n / 2];
cout << median << "\n";
// 3. 최빈값
// map: 각 숫자를 key로, 나타난 횟수를 value로 저장
// map은 자동으로 key를 오름차순 정렬함
map<int, int> freq;
for (int x : arr) {
freq[x]++; // x가 나타날 때마다 카운트 증가
}
// 가장 많이 나타난 횟수(최대 빈도) 찾기
int maxFreq = 0;
for (auto& p : freq) {
// p.first: 숫자, p.second: 나타난 횟수
maxFreq = max(maxFreq, p.second);
}
// 최대 빈도를 가진 모든 숫자들을 modes 벡터에 모으기
// (최빈값이 여러 개일 수 있음)
vector<int> modes;
for (auto& p : freq) {
if (p.second == maxFreq) {
modes.push_back(p.first);
}
}
// 최빈값이 여러 개면 두 번째로 작은 값 선택
// 최빈값이 1개면 그것 선택
int mode = (modes.size() > 1) ? modes[1] : modes[0];
cout << mode << "\n";
// 4. 범위
// 배열이 정렬되어 있으므로 arr[n-1]이 최댓값, arr[0]이 최솟값
int range = arr[n - 1] - arr[0];
cout << range << "\n";
return 0;
}
복잡도 분석
- 시간 복잡도:
- 입력 및 합계 계산: O(N)
- 정렬: O(N log N)
- 빈도 계산 및 최빈값 찾기: O(N log N) (map 삽입/접근) 또는 O(N) (vector 사용 후 정렬) - 여기서는 map을 사용했으므로 O(N log N)
- 최빈값 후보 탐색: O(N) (map 크기)
- 범위 계산: O(1)
- 전체 시간 복잡도: O(N log N) (정렬 및 map 연산에 의해 지배됨)
- 공간 복잡도:
vector arr: O(N)map freq: O(N) (최대 N개의 고유한 숫자가 저장될 수 있음)vector modes: O(N) (최악의 경우 모든 숫자가 최빈값이 될 수 있음)- 전체 공간 복잡도: O(N)
배운 점
이 문제를 통해 여러 통계값을 계산하는 방법을 익혔습니다. 특히, 최빈값을 구할 때 map을 사용하여 빈도를 효율적으로 관리하고, 최빈값이 여러 개일 경우 두 번째로 작은 값을 선택하는 로직을 구현하는 방법을 배울 수 있었습니다. 또한, 산술평균에서 소수점 처리를 위해 double 형 변환과 round() 함수의 사용법을 다시 확인할 수 있었습니다.