컴공댕이 공부일지
[ C++/cpp ] 백준 (2108 통계학) ⭐최빈값 구하기, 최장 길이 부분 수열 본문
백준 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 등등등 잘 마치는 보람찬 여름학기가 되길 ..! 아쟈
'문제 풀이 > 코딩 문제 풀이 모음' 카테고리의 다른 글
[ C++/cpp ] 백준 (1654 랜선 자르기) ⭐이분 탐색 💦 (0) | 2024.07.20 |
---|---|
[ C++/cpp ] 백준 (11561 좌표 정렬하기2) ⭐pair vector 정렬, 비교함수 (0) | 2024.07.18 |
[ C++/cpp ] 백준 (1018 체스판 다시 칠하기) ⭐브루트포스 알고리즘 (1) | 2024.03.29 |
[ C++/cpp ] 백준 (2839 설탕 배달) ⭐그리디 알고리즘 (1) | 2024.03.28 |
[ C++/cpp ] 백준 (11268 절댓값 힙) ⭐자료구조, 우선순위 큐 (0) | 2024.03.28 |