[BaekJoon 2108][⚪2] 통계학
❓ 문제
🎯 난이도
Silver ⚪2
🧠 풀이
1. 내 풀이 (동적 배열 + 해시 맵)
- 알고리즘
Mathematics,Data Structure,Set & Map,Hashing
- 설명
vector, unordered_map를 사용하는 풀이이다.
평균, 중앙값, 범위를 구하기 위해 vector와 sort 정렬 알고리즘을 사용했고, 최빈값을 구하기 위해 unordered_map을 사용했다. unordered_map은 값이 중복이 안되고 카운팅이 가능하기 때문에 한 선택이었지만, 지금 생각해보니 '공간 할당'과 '속도' 면에서 아쉬운 점이 있어서 최선의 방법은 아닌 것 같다.
주의할 점은 평균을 구할 때 합이 커질 경우를 대비해 long long으로 선언하는 것과, round로 평균을 낼 때 부동소수점형으로 반환되기 때문에 -0 같은 예외를 방지하기 위해 정수형으로 캐스팅하는 것이다.
sort의 시간 복잡도가 가장 크므로 전체적인 시간 복잡도는 O(N log N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
unordered_map<int, int> umapMost{}; // 최빈값 구하기 위한 unordered_map
vector<int> vecNum{};
vecNum.reserve(iN);
long long llSum{}; // Sum이 int의 한계를 넘을 수 있으므로 long long 선언
int iMost{}; // 최빈값의 빈도를 저장
for(int i = 0; i < iN; ++i)
{
int iInput{};
cin >> iInput;
llSum += iInput;
vecNum.push_back(iInput);
++umapMost[iInput];
iMost = max(iMost, umapMost[iInput]); // 빈도 갱신
}
vector<int> vecMost{}; // 최빈값들을 따로 모아주기 위한 vector
vecMost.reserve(iN);
// 최빈값의 빈도와 같은 값들만 vector에 할당
for(auto iter = umapMost.begin(); iter != umapMost.end(); ++iter)
{
if(iter->second == iMost)
{
vecMost.push_back(iter->first);
}
}
sort(vecNum.begin(), vecNum.end());
sort(vecMost.begin(), vecMost.end());
// 정수 뽑아내기 위해 llround 사용, 평균은 -4000 <= iMean <= 4000이므로 int 경계 내라는걸 명확히 하기 위해 int로 캐스팅 (필수적인 건 아님)
// 정수로 안하면 -0 같은 예외 발생
int iMean{ static_cast<int>(llround(static_cast<double>(llSum) / iN)) };
int iMid{ vecNum[iN / 2] };
iMost = vecMost.size() == 1 ? vecMost[0] : vecMost[1]; // 최빈값이 여러개면 두번째로 작은 값 출력
int iRange{ vecNum.back() - vecNum.front() };
cout << iMean << '\n' << iMid << '\n' << iMost << '\n' << iRange;
return 0;
}
2. 추가 풀이 (동적 배열 + 배열)
- 알고리즘
Mathematics,Data Structure
- 설명
vector, 배열를 사용하는 풀이이다.
unordered_map을 사용하는 대신 배열만을 사용해서 미리 공간을 할당한 뒤, 최빈값을 추출하는 방식이다.
로직 상에서의 바뀐 부분은 이 부분 밖에 없지만, unordered_map을 사용하지 않음으로써 '사용 메모리'도 확 줄고, 배열의 좋은 '캐시 친화성' 덕분에 속도도 빨라진다. 그 대신 최빈값이 여러개인 경우를 대비한 로직을 추가해야 한다는 점을 주의하자.
이 풀이 또한 시간 복잡도는 위와 같은 O(N log N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iN{};
cin >> iN;
vector<int> vecNum{};
vecNum.reserve(iN);
int arrCnt[8001]{}; // 최빈값 카운팅 배열
long long llSum{}; // Sum이 int의 한계를 넘을 수 있으므로 long long 선언
for(int i = 0; i < iN; ++i)
{
int iInput{};
cin >> iInput;
llSum += iInput;
vecNum.push_back(iInput);
++arrCnt[iInput + 4000];
}
sort(vecNum.begin(), vecNum.end());
// 정수 뽑아내기 위해 llround 사용, 평균은 -4000 <= iMean <= 4000이므로 int 경계 내라는걸 명확히 하기 위해 int로 캐스팅 (필수적인 건 아님)
// 정수로 안하면 -0 같은 예외 발생
int iMean{ static_cast<int>(llround(static_cast<double>(llSum) / iN)) };
int iMid{ vecNum[iN / 2] };
int iRange{ vecNum.back() - vecNum.front() };
// 최빈값의 빈도 찾아내기
int iMaxFreq{};
for(int i = 0; i < 8001; ++i)
{
iMaxFreq = max(iMaxFreq, arrCnt[i]);
}
int iMost{}; // 최빈값 저장
bool bFirst{}; // 가장 처음 나온 최빈값인지를 위한 flag 변수
for(int i = 0; i < 8001; ++i)
{
if(arrCnt[i] == iMaxFreq)
{
iMost = i - 4000; // 최빈값 갱신
// 처음 나온 최빈값이면 bFirst = true
if(!bFirst)
{
bFirst = true;
}
// 아니면 break 해서 두번째로 작은 값으로 출력
else
{
break;
}
}
}
cout << iMean << '\n' << iMid << '\n' << iMost << '\n' << iRange;
return 0;
}
💭 후기
값이 중복되지 않고 카운팅을 해야한다는 시점에서 처음에 배열을 떠올렸지만, 최빈값이 여러개인 경우를 생각했을 때 unordered_map을 사용하는 쪽이 로직 상으로는 더 쉬울 것 같아서 첫 번째 풀이를 생각해냈다. '가독성'을 생각했을 땐 첫 번째 풀이겠지만, '메모리 사용'이나 '속도'면에서 두 번째 풀이가 확실히 좋으므로 코테에서는 두 번째 풀이가 맞는 것 같다.
- 첫 번째 풀이 :
88ms,6340KB - 두 번째 풀이 :
68ms,3980KB
이 정도 차이라면 가독성보다는 성능을 우선시해도 되는 차이 같다.
Comments