1. 미션 제목
친구들과 최단거리에 있는 집 구하기
2. 지시문
David의 친구들은 한 거리에 모두 모여살고 있습니다. David은 이번에 친구들이 살고 있는 거리로 이사를 가기로 했는데, 친구들의 집에서 거리가 가장 가까운 집을 구해서 그곳으로 이사를 하고 싶습니다. 모두 같은 거리에 살고 있으므로 아래 그림과 같이 친구들의 집 위치를 수직선 상에 표현할 수 있고, 그 때 집은 항상 정수점 위에만 있다고 가정합니다.
이 때, David이 어느 위치에 있는 집으로 이사를 가야 모든 친구들의 집까지의 거리의 합이 최소가 될 수 있는지 생각해보고 이를 출력하는 프로그램을 작성해봅시다. 그리고 이 때 이 프로그램의 시간복잡도(Big O)가 얼마나 되는지 얘기해봅시다. 어떻게 하면 시간복잡도를 최소화할 수 있을지도 같이 생각해봅시다. 집이 있을 수 있는 위치는 한자리 정수로만 구성되며, 숫자를 입력 받는 부분은 따로 구현하지 않고 프로그램 내부에 배열로 선언하는 것으로 가정하고, 숫자에는 중복이 있을 수 있습니다.
예)
입력값: 12345 -> 출력값: 3
입력값: 2224 -> 출력값: 2
3. 핵심 개념
#거리의합이최소 #중앙값 #평균값