[C++백준] 실버 4/ 2108번 통계학

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

2108번: 통계학

#include <iostream>
#include<map>
#include<algorithm>
#include<vector>
#include<cmath>
 
using namespace std;
 
 
int main() {
    
    vector<int>v;
    int arr[8001] = {0,};
    
    int n;
    double total=0;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        total += num;
        v.push_back(num);
        arr[num + 4000]++;
    
    }
 
    int flag = 0;
    int max = 0;
    sort(v.begin(),v.end());
 
    for (int i = 0; i < 8001; i++) {
        if (arr[i] > max) {
            max = arr[i];
            flag = i; //최빈값 중 첫번째 값
        }
    }
    
    for (int i = flag + 1; i < 8001; i++) {
        if (arr[i] == max) {
            flag = i;
            break;
        }
    }
 
    int mean = round(total / n);
    printf("%d\n", mean);
    int mid = n/2;
    printf("%d\n", v[mid]);
    printf("%d\n", flag-4000);
    printf("%d\n", v[n - 1] - v[0]);
 
    
    
 
    return 0;
}
 

 

이 문제는 vector로 풀다가 계속 시간초과나서 결국 다른 사람의 코드를 봤다.

결국 문제가 까탈스러운것은 최빈값 때문이였는데 arr[원소]=원소가 중복된 개수 이런식으로 설정해줘야 한다.

예를 들어 -8이 1번 나왔다면 arr[-8]=1이 되는데 음수인덱스는 불가능하다.

이때 문제의 조건이 입력되는 정수가 -4000부터 4000까지 라는 것이다. 그렇다면 인덱스는 총 8001개로 한정지을 수 있다!

그래서 arr[8001]이라고 초기화를 해주고 입력받을때 arr[num+4000]을 해주면 나중에 인덱스-4000을 하면 되니까 음수인덱스를 자유자재로 컨트롤 할 수 있다. 

 

 if (arr[i] > max) {

            max = arr[i];

            flag = i; --> 최빈값 중 첫번째로 나온 값을 flag에 저장해놓고

 

        }

for (int i = flag + 1; i < 8001; i++) {

--> flag+1을 통해 첫번째 최빈값를 제외시켜서 두번째 최빈값을 찾는다.

        if (arr[i] == max) {

            flag = i;

            break; --> 두번째 최빈값만 찾으면 되니까 찾고 나서는 반복문을 빠져나온다.

        }

    }

 

처음썼던 코드 + 틀린 이유 생각

 

처음에는 vector를 통해 v<중복되는 개수, 원소> 이런식으로 저장해주었다.

int count = 0;
 
vector<pair<int, int>> v;
 
int count = 0;
 
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) {
        int current = 0;
        for (int j = i; j < n; j++) {
            if (arr[i] == arr[j]) {
                current++;
            }
            if (current >= count) {
                count = current;
            }
        }
        v.push_back(pair<int, int>(count, arr[i]));//개수 원소
}
    
vector<int>mode;
for (int i = 0; i < v.size(); i++) {
        if (v[i].first == count) {
            mode.push_back(v[i].second);
        }
}
//중복제거(이미 정렬은 arr부터 정렬해놔서 상관 x)
unique(mode.begin(), mode.end());
if (mode.size() == 1) {
        cout << mode.front() << endl;
    }
else {
        mode.erase(mode.begin() + 0);
        cout << mode.front() << endl;
    }