컴공댕이 공부일지

[ C++/cpp ] 백준 (2108 통계학) ⭐최빈값 구하기, 최장 길이 부분 수열 본문

문제 풀이/코딩 문제 풀이 모음

[ C++/cpp ] 백준 (2108 통계학) ⭐최빈값 구하기, 최장 길이 부분 수열

은솜솜솜 2024. 7. 11. 04:02
728x90

백준 2108번 통계학

(실버 3)

 

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

 

 

 

 

 

 

(정답 코드)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int findMode(const vector<int>& num, int max_length) {
    
    if(num.size() == 1) return num[0]; // 값이 하나뿐이면 그 값이 최빈값
    
    int mode;
    int l=0;
    bool finded = false;
    int start = 0;
    int end = 0;
    
    for(int i=0; i<num.size()-1; i++) {
        
        
        if(num[i] != num[i+1]) {
            end = i+1;
            l = end - start ; // 동일 숫자 부분 수열 길이
        }
        
        else if (i==num.size()-2) l = num.size()-start; // 가장 끝의 부분수열 길이
        
        if (l == max_length) { // 수열 길이가 최빈값의 수열 길이와 같다면,
            mode = num[i]; // 현재값은 최빈값이므로 저장

           if(finded) return mode; // 만약 이전에도 최빈값이 발견되었다면, 현재가 두번째로 작은 최빈값
            finded = true; // 아직 리턴 안됐다면, finded를 true로 태그
        }
        start = end; // 시작점 갱신
        l=0;
    }
    
    return mode;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n, temp, avg, median, mode, range;
    vector<int> num; 
    vector<int> cnt(8001, 0); // 8001칸 0으로 초기화
    
    cin >> n;
    int sum = 0;
    int max = -4000;
    int min = 4000;
    int cnt_max = 0; // 최빈값 찾는 데 쓸 변수
    
    for(int i=0; i<n; i++) {
        cin >> temp;
        if(min>temp) min = temp;
        if(max<temp) max = temp;
        
        num.push_back(temp);
        sum += temp;
        
        cnt[temp+4000]++;
        if(cnt_max < cnt[temp+4000]) cnt_max = cnt[temp+4000]; // 최빈값 횟수 갱신
    }

    sort(num.begin(), num.end()); // 벡터 오름차순 정렬

    // 평균, 중앙값, 최빈값, 범위 연산
    avg = round( (double)sum / n );
    median = num[n/2];
    mode = findMode(num, cnt_max);
    range = max-min;
    
    cout << avg << "\n" << median << "\n" << mode << "\n" << range;
    
    return 0;
}

 

 

🔎 풀이

 

1.  평균

입력받으면서 수들의 총합 sum 구해두기. 그리고 sum / n !  

 이때 정수끼리의 나눗셈이라 소수를 냅다 날려버리기 때문에 반올림을 위해선 소수로 형변환을 해야하고, 반올림은 round 함수를 사용했다.

 

2.  중앙값

입력받은 수 오름차순 정렬한 수에 n/2번째 수 출력 ! 간단하다 입력되는 수가 무조건 홀수개라 뭐 더 고려할 필요도 없다

 

3. 최빈값

 먼저 입력받을 때, 최빈값의 횟수를 구해둠. 그리고 입력받은 숫자들 오름차순 정렬한 후에, 앞서 구한 최빈값 갯수와 같은 수를 찾는다. 이 과정에서 각 수의 등장 횟수(?)는 부분 수열 길이로 구했다. 수가 다른 수로 바뀌기까지 길이를 구해서, 이 수의 횟수가 최빈값 횟수와 같으면 저장 ! 그리고 2번째로 저장되는 순간 리턴하기 ~

최빈값 구하는 과정 글로 쓰니 뭔가 설명이 어려워서.. 간단한 그림 첨부

 

4. 범위

애초에 입력받으면서 min, max 값 갱신시켜둠. 둘 뺴면 범위 나오지요 ~

 

 

 

 

 

 

📖 Trouble Shooting

1. 평균에서 반올림하는 거 쪼끔 헷갈렸는데

cmath 헤더에 round 함수 사용했다 ! 
PS를 하도 안해가지구.. 함수 전달하고 벡터 size()함수 이런 짜잘한 거 다 까먹어서 헷갈렸닿ㅎ

 

2. 최빈값 구하는 함수......

새벽에 잠오는 상태로 풀어서 그런가.. 어렵지 않은데 조금씩 삐끗삐끗했다

문제 자체는 간단한데 예외 케이스가 많아서 조심해야함..ㅎㅅㅎ

 

일단 최빈값은 수들 모두 입력받고, 입력 받으면서 그 숫자의 카운트도 같이 저장했다

그렇게 최빈값의 등장 횟수를 찾고, 그 값과 부분 수열 길이가 같으면 최빈값으로 저장한다.

 

그리고 2번째로 작은 최빈값, 즉 오름차순 수열에서 이미 최빈값을 찾아뒀는데(finded함수가 true인데) 또 찾았다??

그러면 이게 2번쨰로 작은 최빈값이니깐 즉시 리턴한당.

 

풀이 자체는 쉬운데 졸려서 그런가 동일한 숫자들의 부분 수열 길이 구하는데서 좀 정신 못차린듯

1) 달라지는 지점에서 end 마크를 찍는데, 벡터 마지막 끝은 어떻게 처리할지 여기서 좀 헷갈렸구

2) 현재 숫자의 수열 길이 l을 초기화 안하는 바부같은 짓을 해서 또 틀렸닿ㅎ

 

 

 

 

 

 

사담

 

아 졸령 빨리 잘래.......... 4시 22분이다 왁 낮밤 지대로 바뀜 ㅎㅎ..

아니 근데 진짜로 ps 꾸준히 해야지 너어어무 오랜만에 하려니까 뭔가 손이 굳은 느낌..

오늘 알튜비튜 튜터 모임다녀오고 급 공부할 마음이 들어서 (누가 누굴 가르치나 싶었나보다)

지인짜 오랜만에.. 컴퓨터에 앉아따

 

종강하고 논문이랑 알켐, 엔비전 등등등 일로 바빴구, 이별의 여파와 ^^.. 또 본가도 몇 달 만에가서 좀 휴식했는데

이제 돌아오니 밀린 공부가 나를 반기고 있는.. 흑흑ㅎ긓긓ㄱ

그래두 바빠두 꾸준히 잔디 심쟈아.. umc aimers 등등등 잘 마치는 보람찬 여름학기가 되길 ..! 아쟈

 

728x90
Comments