[부스트 코딩 뉴비 챌린지 2020] week4_미션02

✔︎ 미션 2.

1. 미션 제목
친구들과 최단거리에 있는 집 구하기

 

2. 지시문
David의 친구들은 한 거리에 모두 모여살고 있습니다. David은 이번에 친구들이 살고 있는 거리로 이사를 가기로 했는데, 친구들의 집에서 거리가 가장 가까운 집을 구해서 그곳으로 이사를 하고 싶습니다. 모두 같은 거리에 살고 있으므로 아래 그림과 같이 친구들의 집 위치를 수직선 상에 표현할 수 있고, 그 때 집은 항상 정수점 위에만 있다고 가정합니다.

이 때, David이 어느 위치에 있는 집으로 이사를 가야 모든 친구들의 집까지의 거리의 합이 최소가 될 수 있는지 생각해보고 이를 출력하는 프로그램을 작성해봅시다. 그리고 이 때 이 프로그램의 시간복잡도(Big O)가 얼마나 되는지 얘기해봅시다. 어떻게 하면 시간복잡도를 최소화할 수 있을지도 같이 생각해봅시다. 집이 있을 수 있는 위치는 한자리 정수로만 구성되며, 숫자를 입력받는 부분은 따로 구현하지 않고 프로그램 내부에 배열로 선언하는 것으로 가정하고, 숫자에는 중복이 있을 수 있습니다.

예)
입력값: 12345 -> 출력값: 3
입력값: 2224 -> 출력값: 2
* 2224의 경우 2에 3명이 같이 사는 것으로 보실 수 있지만 문제상 같은 위치에 여러명이 살 수 있다는 가정으로 풀어주세요^^

3. 핵심 개념
#거리의합이최소 #중앙값 #평균값

 

* 본 문제의 경우 문제를 푸는데 도움이 되는 힌트가 있습니다. 알고리즘의 경우 방법을 직접 고민해보고 찾는 것이 중요합니다. 때문에 고민을 하시다가 도저히 풀 수가 없을때 아래의 힌트를 참고해주시길 바랍니다.

-> '         ' 사이를 마우스로 블록을 하면 힌트가 나옵니다.

 '평균값과 중앙값 중에 거리의 합을 최소로 만드는 값은 어떤 것인지 먼저 생각해봅시다.'

 

 

문제 풀이

친구들의 집과 거리 합이 가장 최소가 되려면 친구들의 집을 정수로 나타낸 숫자들의 (1)평균값 (2)중앙값 둘 중 하나가 답이 될 수 있다.

하지만 (1)평균값을 정답으로 할 경우에는 예외의 문제가 생긴다. 예외는 바로 이런 경우이다. 만일 친구들의 집이 1 1 1 9 인 있는 경우, 평균 값은 3이 되지만 사실 결과값은 1이 되어야 한다. 따라서 정답은 (2)중앙값으로 해야 한다.

 

그리고 고려해야 할 문제가 한 가지가 더 있다. 친구들의 수가 짝수인 경우와 홀수인 경우이다. 홀수인 경우에는 바로 중앙값이 나오지만, 짝수인 경우에는 중앙값이 두 가지가 나온다. 예로 들어서 5명이면 중앙값은 3번 째 값이 되지만, 6명인 경우 3번 째로 선택해야 할지, 4번 째 값을 선택해야 할지 고민하는 문제가 발생한다.

이 문제를 나는 3번 째와 4번 째 두 값 중에서, 평균값에 더 가까운 값을 선택하도록 했다.

그래서 평균값을 구하는 avg()함수를 만들었고 평균값에서 각 값을 빼고 제곱한 수를 비교하여 숫자가 더 작은 값을 선택하도록 하였다. 제곱한 수로 비교한 이유는 평균값에서 뺀 값이 양수일 수도 있고 음수일 수도 있기 때문이다.

그 결과 아래와 같이 코드를 작성하니 내가 원하는 결과값이 잘 나오는 것을 확인할 수 있었다.

#include <stdio.h>
#include <math.h>   //pow() : 제곱근구하기. pow(base, 제곱)
#include <cs50.h>   //get_int

/*친구들과 최단거리에 있는 집 구하기*/

/*입력값 중 중앙값 찾는 프로그램.
먼저 오름차순으로 정리한 후, 중앙값을 출력한다

개수가 홀수인 경우, 중앙값 출력
개수가 짝수인 경우, 중앙의 두 값중에서 평균에 더 가까운 값을 출력*/

int* bubble_sort(int a[], int length);
int midnum(int a[], int length);
float average(int a[], int length);
float pow_num(float avg, int num);

int main(void){
    const int LENGTH = get_int("친구들이 몇 명인가요?\n");

    printf("%i명 친구들의 집을 숫자로 나타내 주세요.\n", LENGTH);

    int num[LENGTH];

    for(int i = 0; i < LENGTH; i++){
        num[i] = get_int("(%d) ",i+1);
    }

    int* num_sorted = bubble_sort(num, LENGTH);

    int mid = midnum(num_sorted, LENGTH);
    printf("%d\n", mid);


    return 0;
}

int* bubble_sort(int a[], int length){
    int temp;

    for(int i = 0; i < length; i++){
        for(int j = 0; j < length - 1 - i; j++){
            if(a[j] > a[j+1]){
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
    return a;
}

int midnum(int a[], int length){
    int mid;
    float avg = average(a, length);

    if(length%2 == 0){ //짝수개인 경우
        if(pow_num(avg, a[length/2]) > pow_num(avg, a[length/2 + 1])){
            mid = a[length/2 + 1];
        }else{
            mid = a[length/2];
        }
    }else{ //홀수개인 경우
        mid = a[length/2];
    }
    return mid;
}

float average(int a[], int length){
    int sum;
    float avg;

    for(int i = 0; i < length; i++){
        sum = sum + a[i];
    }
    avg = (float)sum/(float)length;
    return avg;
}

float pow_num(float avg, int num){
    return pow(avg - num, 2);
}