240124 몸짱 트레이너 라이언의 고민

private int n;

public int solution(int n, int m, int[][] timetable) {
	this.n = n;
	int maxNum = getMaxNum(m, timetable);

	if (maxNum == 1)
		return 0;
	if (maxNum > (n * n + 1) / 2)
		return 1;

	int dis = 1;

	while (can(dis + 1, maxNum)) {
		dis++;
	}

	return dis;
}

private boolean can(int dis, int maxNum) {
	List<Point> pointList = new ArrayList<>();

	for (int i = 0; i < n; i++) {
		pointList.add(new Point(i));

		for (int k = i + 1; k < n * n; k++) {
			if (valid(k, pointList, dis)) {
				pointList.add(new Point(k));
			}
		}

		if (pointList.size() >= maxNum)
			return true;
		pointList.clear();
	}

	return false;
}

private boolean valid(int k, List<Point> pointList, int dis) {
	for (Point p : pointList) {
		if (p.getDistance(k) < dis)
			return false;
	}
	return true;
}

private int getMaxNum(int m, int[][] timetable) {
	Set<Integer> uniqueTimes = new HashSet<>();

	for (int i = 0; i < m; i++) {
		uniqueTimes.add(timetable[i][0]);
		uniqueTimes.add(timetable[i][1]);
	}

	List<Integer> sortedTimes = new ArrayList<>(uniqueTimes);
	Collections.sort(sortedTimes);

	int[] peopleNums = new int[sortedTimes.size()];
	int max = 0;

	for (int i = 0; i < m; i++) {
		int from = Collections.binarySearch(sortedTimes, timetable[i][0]);
		int to = Collections.binarySearch(sortedTimes, timetable[i][1]);

		for (int j = from; j <= to; j++) {
			peopleNums[j]++;
			max = Math.max(max, peopleNums[j]);
		}
	}

	return max;
}

class Point {
	int i;

	public Point(int i) {
		this.i = i;
	}

	public int getDistance(int num) {
		return Math.abs(this.i / n - num / n) + Math.abs(this.i % n - num % n);
	}
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/1838