[C] 친구들과 최단거리에 있는 위치 구하기

www.notion.so/2-13236306f1d1473b89ec0b7dc3c04cfe

✔︎ 미션 2.친구들과 최단거리에 있는 집 구하기

✔︎ 미션 2.

1. 미션 제목

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

2. 지시문

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

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

예)

입력값: 12345 -> 출력값: 3

입력값: 2224 -> 출력값: 2

• 2224의 경우 2에 3명이 같이 사는 것으로 보실 수 있지만 문제상 같은 위치에 여러명이 살 수 있다는 가정으로 풀어주세요^^

3. 핵심 개념

#거리의합이최소 #중앙값 #평균값

• 본 문제의 경우 문제를 푸는데 도움이 되는 힌트가 있습니다. 알고리즘의 경우 방법을 직접 고민해보고 찾는 것이 중요합니다. 때문에 고민을 하시다가 도저히 풀 수가 없을 때 아래의 힌트를 참고해주시길 바랍니다.
• '평균값과 중앙값 중에 거리의 합을 최소로 만드는 값은 어떤 것인지 먼저 생각해봅시다.'

 

나의 풀이

#include<stdio.h>

int main(void) {
    int location[] = {2, 2, 2, 4};
    int size = sizeof(location)/sizeof(location[0]);

    // 홀수
    if(size % 2) {
        printf("David야! %d(으)로 이사와!\n", location[size/2]);
    }
    // 짝수
    else {
        printf("David야! %d부터 %d까지 아무데나 이사와도 돼!\n", location[size/2 - 1], location[size/2]);
    }
}

친구들의 집 = {a, b, c, d} (오름차순으로 정렬된 정수)

David의 집 = n

거리 = |n - a| + |n - b| + |n - c| + |n - d|

위와 같이 된다. 이때 거리가 최소가 되는 n을 찾으면 되는 것이다.

 

case 1 ( n < a )

    거리 : -4n + ( a + b + c + d )

case 2 ( a ≤ n < b )

    거리 : -2n + ( -a + b + c + d )

case 3 ( b ≤ n < c )

    거리 : -a -b + c + d

case 4 ( c ≤ n < d )

    거리 : 2n + ( -a -b -c + d )

case 5 ( d ≤ n )

    거리 : 4n - ( a + b + c + d )

 

각 case에서 거리가 최소가 되는 경우는 다음과 같다

case 1 ( n = a - 1 )

    거리 : -3a + b + c + d + 4

case 2 ( n = b - 1 )

    거리 : -a -b + c + d + 2

case 3 (이 구간에서는 항상 같은 거리가 추출됨)

    거리 : -a -b + c + d

case 4 ( n = c )

    거리 : -a -b + c + d

case 5 ( n = d )

    거리 : -a -b -c + 3d

 

case1에서 case2를 빼면 -2a +2b +2 가 나온다. b는 a 이상이므로 case1이 더 큰 것이다. case2의 최소 거리가 더 짧은 것으로 판단할 수 있다.

 

case2에서 case3를 빼면 2가 나온다.

case3의 최소 거리가 더 짧은 것으로 판단할 수 있다.

 

case3와 case4의 최소 거리는 같은 것으로 나온다.

 

case4에서 case5를 빼면 2c - 2d가 나온다. d는 c 이상이므로 case5가 더 큰 것이다.

 

결과적으로 보면 b ≤ n ≤ c 범위에서 최소 거리가 나오는 것이다.

David는 b ≤ n < c 범위 내에 살면 모든 친구들과 가깝게 살 수 있게 된다.

 

위의 수학적 검증을 통해 모든 친구들과의 집까지의 최소 거리는 b ≤ n ≤ c 범위인 것을 알게 되었다. 즉, 알고리즘의 복잡도는 O(1)이 된다.

 

위와 같은 방법으로 친구가 5명일 때를 계산해보면

친구들의 집이 {a, b, c, d, e} 일 때 David의 집은 c에 있을 때 최소 거리가 된다.

 

일반화를 시켜보면 홀수일 때는 친구들의 집의 중간 값이 거리의 최솟값이 되고, 홀수일 때는 친구들의 집의 중간 두 집 사이의 모든 값이 최솟값이 된다.