[c++] 2108 통계학

❔ 문제

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

 

🔍 문제 요약

• 입력
  • 첫 줄에 수의 개수 N (1 ≤ N ≤ 500,000)
  • 둘째 줄부터 N개의 정수 (-4000 이상 4000 이하)
• 목표
  • 산술평균 (소수 첫째 자리에서 반올림)
  • 중앙값 (정렬된 수열의 중앙값)
  • 최빈값 (여러 개일 경우 두 번째로 작은 값)
  • 범위 (최댓값 - 최솟값)

 

---

⛔️ 틀린 코드 

int n; 
double sum=0;

//... 생략 

cout << std::fixed << sum/n << '\n'; // -0 출력될 수 있음

sum / n이 -0.333...일 때 -0이 출력되는 문제가 발생함.

이는 C++에서 double 형이 -0.0을 가질 수 있기 때문에 생김.

 

C++에서 -0.0이 존재하는 이유?

C++에서 float, double은 대부분 IEEE 754 표준을 따르는데, 이 표준에서는 +0.0과 -0.0을 명확히 구분한다고 한다. 

목적은 부호 있는 값의 극한 표현이 필요할 때 사용하기 위해서... 즉 -0.0은 실수 계산의 정밀성과 방향성 보존을 위한 기능. 

 

하지만,

비교 연산	-0.0 == 0.0 → true (값은 같음)
signbit	std::signbit(-0.0) → true  std::signbit(0.0) → false

-> 내부적으로 비트만 다름! 

 

구조를 살펴보면 double 형식은 64비트로 구성돼 있고, 아래와 같은 구조를 가진다.

1 bit	부호 비트 (sign bit)
11 bits	지수부 (exponent)
52 bits	가수부 (fraction, mantissa)

 

• +0.0과 -0.0의 내부 비트

	+0.0	-0.0
Sign bit	0	1
Exponent	00000000000	00000000000
Fraction	000...000 (52개)	000...000 (52개)

 

---

🔑 해결 전략: 이분 탐색 (Binary Search)

 

💙 Step 1: 자료 수집

vector<int> list;
map<int, int> m;
double sum = 0;

• list로 정렬하여 중앙값 계산
• map으로 각 숫자의 등장 횟수 저장
• sum으로 평균 계산

 

💙 Step 2: 정답 출력

산술평균 (-0 출력 방지 처리)

double avg = sum / n;
if (-0.5 <= avg && avg < 0.5) cout << 0 << '\n';
else cout << std::fixed << avg << '\n';

처음에는 위처럼 처리했다가 round 이용하는 방법이 있다는걸 알고 round로 고쳤다. 

cout <<(int)round(sum / n) << '\n';

double에는 -0과 0을 구분하기 때문에 int로 형변환을 시켜준다. 

 

🧠 int 에서의 0

C++의 int는 2의 보수(2’s complement) 방식으로 음수를 표현 -> 이 방식에서는 0은 오직 하나만 존재

1000 0000 0000 0000 0000 0000 0000 0000

위와 같은 2진수가 있을때, 

• 총 32비트 = int (C++에서 기본적으로 int는 4바이트 = 32비트)
• 맨 앞이 1이므로 → 음수
• 이건 2의 보수 방식으로 표현된 정수임!

 

이걸 해석해보면,

1. 부호확인 : 첫 비트가 1 → 음수
2. 2의 보수 → 양수로 변환
   1. 1’s complement (비트 반전) : 0111 1111 1111 1111 1111 1111 1111 1111
   2. +1 하기 : 1000 0000 0000 0000 0000 0000 0000 0000 -> 즉, 절댓값: 2,147,483,648

최종적으로 저 비트를 int로 해석하면: -2,147,483,648

 

정리하면,

이진수	10000000000000000000000000000000
정수값 (int)	-2,147,483,648
의미	int에서 표현 가능한 최솟값!!!
상수	INT_MIN (#include <limits.h>에 정의됨)

 

중앙값

    sort(list.begin(),list.end());
    cout<<list[n/2]<<'\n';

정렬 후 중앙에 있는 값 접근 

 

최빈값 

for (auto it = m.rbegin(); it != m.rend(); ++it) {
    if (it->second > max_cnt) { ... }
    else if (it->second == max_cnt) { ... } // 두 번째로 작은 값
}

map 역순 순회로 최빈값이 중복일 때 두 번째로 작은 값 반환

 

범위 

cout<<m.rbegin()->first-m.begin()->first<<'\n';

map 에서 자동정렬해주니까 처음요소와 마지막 요소의 차이를 구해줌 

 

 

---

✅ 정답 코드 

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

vector<int> list;
int main(){
    int n; cin>>n; // N(1 ≤ N ≤ 500,000)
    map<int,int> m;
    double sum=0;
    for(int i=0,tmp;i<n;i++){
        cin>>tmp; 
        m[tmp]++;
        list.push_back(tmp);
        sum+=tmp;
    }
    
    // 산술평균
    cout <<(int)round(sum / n) << '\n';

    // 중앙값
    sort(list.begin(),list.end());
    cout<<list[n/2]<<'\n';
    
    // 최빈값 
    int max_cnt=0,max_num=0;
    int prev_cnt=0,prev_num=0;
    for(auto it=m.rbegin();it!=m.rend();it++){
        if(it->second > max_cnt){
            max_cnt=it->second;
            max_num=it->first;
            continue;
        }

        if(it->second == max_cnt){
            prev_num=max_num;
            prev_cnt=max_cnt;
            max_num=it->first;
        }
    }

    if(max_cnt==prev_cnt) cout<<prev_num<<'\n';
    else cout<<max_num<<'\n';

    // 범위
    cout<<m.rbegin()->first-m.begin()->first<<'\n';
}

 

⏱️ 시간복잡도 분석

입력 및 카운팅	O(N)
정렬 (중앙값)	O(N log N)
최빈값 탐색	O(N) (map 순회)
총합	O(N log N)

 

 

---

🏃‍♀️ 다른 코드

• int cnt[8001] 배열로 카운팅
• 평균 계산 : sum += cnt[i] * idx;
• 누적합으로 중앙값 계산

int c = 0;           // 누적 개수

c += cnt[i];
if(mid == 9999 && n/2+1 <= c) mid = idx;

누적 개수 c가 n/2 + 1 이상이 되면 그 시점의 값이 중앙값 

• 정렬 불필요 → O(N)