9088. 다이아몬드

가장 큰 값과 가장 작은 값은 차이가 K이하여야 되고 그 안에 있는 다이아몬드는 모두 포함되어야 되기 때문에 정렬을 이용하는 것이 좋다. 

정렬한 이후, 모든 값에서 모든 경우의 수를 생각해서 가장 max값을 선택하면 된다. 

처음에는 처음과 끝에서부터 한칸이 줄여나가면서 풀면 가능할 것이라고 생각했는데 줄여나가는 기준을 찾지 못해서 새로운 방법으로 풀었다. 

#include<stdio.h>
# define MAX_SIZE 1010
int sorted[MAX_SIZE]; // 추가적인 공간이 필요

void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left;
	j = mid + 1;
	k = left;

	/* 분할 정렬된 list의 합병 */
	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}

	// 남아 있는 값들을 일괄 복사
	if (i>mid) {
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	}
	// 남아 있는 값들을 일괄 복사
	else {
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	}

	// 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
	for (l = left; l <= right; l++) {
		list[l] = sorted[l];
	}
}

// 합병 정렬
void merge_sort(int list[], int left, int right) {
	int mid;

	if (left<right) {
		mid = (left + right) / 2;// 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
		merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
		merge_sort(list, mid + 1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
		merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
	}
}
int main(void) {
	int ts = 0;
	scanf("%d", &ts);
	for (int q = 0; q < ts; q++) {
		int N, K;
		scanf("%d %d", &N, &K);
		int list[1010] = { 0 };
		double box = 0;
		for (int i = 0; i < N; i++) {
			scanf("%d", &list[i]);
		}
		int max = 0;
		merge_sort(list, 0, N - 1);
		for (int i = 0,j=0; i < N; i++) {
			int box = 0;
			for (j = i; j < N; j++) {
				if (list[j] - list[i] > K)
					break;
			}
			if (max < j-i)
				max = j-i;
		}
		printf("#%d %d\n", q + 1, max);
	}
	return 0;
}