[HSAT 7회 정기 코딩 인증평가 기출] 자동차 테스트
💥 문제
자동차 제조 과정에서는 다양한 테스트를 통해 해당 자동차가 잘 만들어졌는지를 평가합니다.
이러한 평가 지표 중 하나는 자동차의 연비입니다.
자동차의 연비가 높을수록 연료 소비가 적고, 더 많은 거리를 주행할 수 있으므로 이는 자동차가 잘 만들어졌는지의 지표로 사용될 수 있습니다.
만약 3대의 자동차를 테스트하고, 각각의 연비를 측정한다고 가정해봅시다.
첫 번째 자동차의 연비는 9km/L,두 번째 자동차의 연비는 15km/L,세 번째 자동차의 연비는 20km/L이라고 합시다.
이 경우, 중앙값은 15km/L이 됩니다.
따라서 이 데이터에서는 중앙값을 이용하여 자동차의 평균적인 연비를 파악할 수 있으며,이는 자동차 제조 과정에서 테스트의 결과를 평가하는 데 활용될 수 있습니다.
n대의 자동차를 새로 만들었지만 여건상 3대의 자동차에 대해서만 테스트가 가능한 상황입니다.
n대의 자동차의 실제 연비 값이 주어졌을 때,
q개의 질의에 대해 임의로 3대의 자동차를 골라 테스트하여 중앙값이 mi값이 나오는 서로 다른 경우의 수를 구하는 프로그램을 작성해보세요.🌐 코드
[C++]
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int bin_search(vector<int> ary, int mi);
int main(int argc, char** argv)
{
int n, q;
vector<int> n_ary;
cin >> n >> q;
// init & fill n_aray
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
n_ary.push_back(tmp);
}
// sort
sort(n_ary.begin(), n_ary.end());
// q(calc mi)
for (int i = 0; i < q; i++) {
int tmp_q;
cin >> tmp_q;
int idx = bin_search(n_ary, tmp_q);
if (idx > 0) cout << idx * ((n - 1) - idx) << endl;
else cout << 0 << endl;
}
return 0;
}
int bin_search(vector<int> ary, int mi) {
int low = 0, high = ary.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (mi < ary[mid]) high = mid - 1;
else if (mi > ary[mid]) low = mid + 1;
else return mid;
}
return -1;
}[C]
#include <stdio.h>
#include <stdlib.h>
// 오름차순
int compare (void *first, void *second)
{
if (*(int*)first > *(int*)second)
return 1;
else if (*(int*)first < *(int*)second)
return -1;
else
return 0;
}
int binarySearch(int* ary, int size, int mi);
int main(void)
{
int n, q;
int* n_ary;
scanf("%d %d", &n, &q);
n_ary = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
int tmp;
scanf("%d", &tmp);
n_ary[i] = tmp;
}
//sort
qsort(n_ary, n, sizeof(int), compare);
//q(mi)
for (int i = 0; i < q; i++) {
int mi, idx;
scanf("%d", &mi);
idx = binarySearch(n_ary, n, mi);
if (idx > 0) printf("%d\n", (idx * ((n - 1) - idx)));
else printf("%d\n", 0);
}
return 0;
}
int binarySearch(int* ary, int size, int mi) {
int low = 0, high = size - 1;
while(low <= high) {
int mid = (low + high) / 2;
if (mi < ary[mid]) high = mid - 1;
else if (mi > ary[mid]) low = mid + 1;
else return mid;
}
return -1;
}🍮 풀이
이 문제를 보자마자 "아 시간복잡도 에 걸리겠구나" 싶었다..
아니나 다를까 ㅠ _ㅠ 첫트에 시간복잡도에 걸려버림 . . .
n 개의 연비 배열을 만들고, 정렬한 후q개의 mi 의 idx 를 찾아서 계산해주면 된다는 것을 파악한 것까지는 50% 통과 ^ ㅁ ^!
제한시간이 2초고, 제약사항에 1 < mi < 1000000000 으로 되어있길래 O(N) 으로 충분히 될 줄 알았으나, 시간초과에 걸려버리고 말았다.
따라서 순차탐색 으로는 ❌절대❌ 안풀린다.
서칭 해보니까 다들 이진탐색으로 해결하시는 것을 보고, 이진탐색이면 충분히 시간복잡도로 해결이 된다는 것을 깨달아버렸다..
따라서 mi 의 idx 를 찾는 것 까지는 맞지만, 찾는 과정에서 이진탐색 을 사용해주면 된다.
💤 어려웠던 점
- 이진탐색과 같은 다양한 탐색을 활용할 줄 알아야 하는데 그 부분에서 많이 아쉬웠다.
- C언어 연습을 위해서 C++ 로 먼저 풀고 C 로 다시 풀었는데, 생각보다 미세하게 언어가 달라서 헷갈렸다.
이얀조다!