4주차 미션
✔︎ 미션 2.
1. 미션 제목
친구들과 최단거리에 있는 집 구하기
2. 지시문
David의 친구들은 한 거리에 모두 모여살고 있습니다. David은 이번에 친구들이 살고 있는 거리로 이사를 가기로 했는데, 친구들의 집에서 거리가 가장 가까운 집을 구해서 그곳으로 이사를 하고 싶습니다. 모두 같은 거리에 살고 있으므로 아래 그림과 같이 친구들의 집 위치를 수직선 상에 표현할 수 있고, 그 때 집은 항상 정수점 위에만 있다고 가정합니다.
이 때, David이 어느 위치에 있는 집으로 이사를 가야 모든 친구들의 집까지의 거리의 합이 최소가 될 수 있는지 생각해보고 이를 출력하는 프로그램을 작성해봅시다. 그리고 이 때 이 프로그램의 시간복잡도(Big O)가 얼마나 되는지 얘기해봅시다. 어떻게 하면 시간복잡도를 최소화할 수 있을지도 같이 생각해봅시다. 집이 있을 수 있는 위치는 한자리 정수로만 구성되며, 숫자를 입력받는 부분은 따로 구현하지 않고 프로그램 내부에 배열로 선언하는 것으로 가정하고, 숫자에는 중복이 있을 수 있습니다.
예) 입력값: 12345 -> 출력값: 3 입력값: 2224 -> 출력값: 2
- 2224의 경우 2에 3명이 같이 사는 것으로 보실 수 있지만 문제상 같은 위치에 여러명이 살 수 있다는 가정으로 풀어주세요^^
3. 핵심 개념
#거리의합이최소 #중앙값 #평균값
- 본 문제의 경우 문제를 푸는데 도움이 되는 힌트가 있습니다. 알고리즘의 경우 방법을 직접 고민해보고 찾는 것이 중요합니다. 때문에 고민을 하시다가 도저히 풀 수가 없을때 아래의 힌트를 참고해주시길 바랍니다.
tip
'평균값과 중앙값 중에 거리의 합을 최소로 만드는 값은 어떤 것인지 먼저 생각해봅시다.'
😎 제출 답안
#include <stdio.h>
#include <math.h>
int* sort_array(int number[]); // sort by bubble
void print_array(int number[]);
float get_average(int number[]); // get average
float get_distance(float value); // get total distance from each item in arr by value
int arr[] = {1, 2, 7, 9, 1, 5};
int arr_size = sizeof(arr) / sizeof(int);
int main(void) {
int* sorted = sort_array(arr);
printf("정렬된 배열 : ");
print_array(sorted);
float average_value = get_average(sorted);
int center_value = sorted[(int)arr_size / 2];
printf("배열의 중간값 : %d\n", center_value);
printf("배열의 평균값 : %.2f\n", average_value);
float total_distance_average = get_distance(average_value);
float total_distance_center = get_distance(center_value);
printf("평균값을 사용할 경우 총 거리: %.2f\n", total_distance_average);
printf("중간값을 사용할 경우 총 거리: %.2f\n", total_distance_center);
total_distance_average < total_distance_center ?
printf("최소 거리 %.2f 를 가진 좌표 %.2f가 가깝습니다.\n", total_distance_average, average_value) :
printf("최소 거리 %.2f 를 가진 좌표 %d가 가깝습니다.\n", total_distance_center, center_value);
return 0;
}
int* sort_array(int number[]) {
int temp;
for(int i = 0; i < arr_size; i++) {
for(int j = 0; j < arr_size - 1; j++) {
if(number[j] > number[j+1]){
temp = number[j];
number[j] = number[j+1];
number[j+1] = temp;
}
}
}
return number;
}
void print_array(int arr[]) {
for(int i = 0; i < arr_size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
float get_average(int number[]) {
float average = 0;
for(int i = 0; i < arr_size ; i++){
average += number[i];
}
average = average/arr_size;
return average;
}
float get_distance(float value) {
float sum = 0;
for(int i = 0; i < arr_size; i++) {
sum += fabs(arr[i] - value);
}
return sum;
}
배열을 정렬(버블 소트)한 뒤, 중앙값과 평균값을 비교하여 더 효율적인 값을 출력하는 코드입니다.