[백준] 18310 안테나

문제

특정 위치의 집에 특별히 한 개의 안테나를 설치 -> 안테나로부터 모든 집까지의 거리의 총 합이 최소

입력

집의 수 N(1≤N≤200,000)
N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수

출력

안테나를 설치할 위치의 값을 출력 (여러 개의 값이 도출될 경우 가장 작은 값을 출력)

풀이

1. 처음에는 이중반복문을 통해 한 집씩 모두 확인한 경우 시간초과 발생
2. 중간집을 선택할 경우가 가장 최소 위치
   1) 집의 갯수가 짝수, 홀수인지 확인
   2) 짝수인 경우는 house.size()/2-1, house.size()/2가 중간값 -> 비교해서 더 작은 값을 선택

using namespace std;

vector<int> house;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N,temp;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> temp;
		house.push_back(temp);
	}
	
	sort(house.begin(), house.end());

	if (house.size() % 2 == 0) { //집의 수가 짝수인경우
		int f = house[house.size() / 2 - 1];
		int s = house[house.size() / 2];
		
		int ft = 0, st = 0;

		for (int i = 0; i < N; i++) {
			ft += abs(house[i] - f);
			st += abs(house[i] - s);
		}

		if (ft <= st) {
			cout << f << "\n";
		}
		else {
			cout << s << "\n";
		}
	}
	else { //집의 수가 홀수인경우
		cout << house[house.size()/2] << "\n";
	}

	return 0;
}