[정올/JUNGOL] 8573번 모임 장소 (C/C++)

https://jungol.co.kr/problem/8573

* 사용언어 : C언어, C++

 

1. 문제

수직선 위의 x 좌표에 살고 있는 N명이 한 명의 집에 모일 때,

사람들의 이동 비용의 합이 최소가 되려면 어떤 x 좌표에 모여야 하는지 출력

여러 개인 경우 오름차순으로 출력

 

2. 풀이

중위값(median)은 N개의 숫자를 정렬했을 때 중앙에 있는 값을 의미합니다.중위값은 모든 값과의 편차를 더한 값(이 경우 이동 비용의 합)이 가장 작다는 특성이 있습니다.따라서 주어진 x 좌표들을 오름차순 혹은 내림차순으로 정렬한 뒤 중위값을 출력하면 됩니다.

 

다만 예제에도 나왔듯 N이 짝수인 경우를 잘 처리해주어야 합니다.

원래 N이 짝수인 경우 중위값은 가운데 2개의 값을 평균내어 계산하는데,

이 문제는 평균을 내지 않고 가운데 2개를 오름차순으로 출력합니다.

 

N이 홀수인 경우에는 가운데 값(N / 2 번째 값) 하나만 출력하면 됩니다.

다만, N이 짝수이더라도 가운데 2개의 값이 같다면 한 번만 출력해야 합니다. (예제 #3)

 

N이 1인 경우도 edge 케이스로 고려해봤는데

이 경우 홀수이면서 N / 2 == 0이 되므로 추가적인 처리를 하지 않아도 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

const int LM = 100000;
int N, arr[LM], tmp[LM];

void mergeSort(int s, int e) {
	if (s >= e) return;
	int m = (s + e) / 2;

	mergeSort(s, m);
	mergeSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (arr[i] < arr[j]) tmp[k++] = arr[i++];
		else tmp[k++] = arr[j++];
	}

	while (i <= m) tmp[k++] = arr[i++];
	while (j <= e) tmp[k++] = arr[j++];

	for (i = s; i <= e; ++i) arr[i] = tmp[i];
}

int main() {
	scanf("%d ", &N);
	for (int i = 0; i < N; ++i) scanf("%d ", &arr[i]);

	mergeSort(0, N - 1);
	
	if (N % 2 == 1 || arr[N / 2 - 1] == arr[N / 2]) printf("%d\n", arr[N / 2]);
	else printf("%d %d\n", arr[N / 2 - 1], arr[N / 2]);
	
	return 0;
}