공유기 설치

문제

언어

  • JavaScript

문제 풀이 step 1

  • 오름차순으로 정렬합니다.
  • 특정 범위 내에서 이진 탐색을 진행합니다.
  • 범위는 1부터 K까지 입니다. (K는 첫 번째 집과 마지막 집의 차이로 합니다.)
  • 이진 탐색을 진행할 때 범위를 두 부분으로 나누는 조건을 결정합니다.
  • 조건은 집 사이의 거리가 mid 값 이상일 때만 설치를 하다가 마지막 집까지 갔을 때 설치한 공유기 개수가 주어진 공유기 개수보다 작은 경우, 같거나 큰 경우로 나눈다.
  • 문제에서는 가장 인접한 공유기의 최대 거리이므로, 반복시마다 실제 설치했던 거리들을 수집해서 최소값을 mid 값으로 바꾼다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const checkPossible = (arr, N, mid, C) => {
	const dist = [];

	//맨 왼쪽과 오른쪽 집에 공유기 설치
	C -= 2;

	let before = 0;
	let final = 0;
	for (let i = 1; i < N; i++) {
		let now = arr[i] - arr[before];
		if (now < mid) continue;

		dist.push(now);
		before = i;
		C -= 1;

		if (C === 0) {
			final = arr[N - 1] - arr[i];
			dist.push(final);
			break;
		}
	}

	// 다 설치 못한 경우
	if (C !== 0) return -1;

	if (final < mid) return -1;

	return Math.min(...dist);
};

const solution = (input) => {
	let [N, C] = input[0].split(" ").map(Number);
	const arr = input
		.slice(1, N + 1)
		.map(Number)
		.sort((a, b) => a - b);

	let res = 1;
	let low = 1;
	let high = parseInt((arr[N - 1] - arr[0]) / (C - 1)) + 1;
	while (low <= high) {
		let mid = parseInt((low + high) / 2);

		let check = checkPossible(arr, N, mid, C);
		if (check === -1) {
			high = mid - 1;
		} else {
			mid = check;
			res = mid;
			low = mid + 1;
		}
	}

	return res;
};

console.log(solution(input));

후기

  • 이진 탐색으로 풀기 위해서는 특정 범위를 정할 수 있어야 하고, 그 범위를 이등분하는 조건을 정할 수 있어야 할 것 같습니다.
  • 처음에는 도저히 어떻게 풀어야 할 지 모르겠어서 종이에 별의 별 공상을 하면서 이상한 방식으로 접근을 했었는데, 결국은 공유기를 mid 값 이상일 때만 설치한다는 생각에 도달하고 나서야 풀 수 있었습니다.
  • 제 생각으로는 일단 첫 번째 집과 마지막 집에 우선적으로 설치를 해야 인접한 공유기의 거리가 최대가 나올 것이라고 판단했습니다. 그 결과 범위를 이등분 하는 조건 함수가 상당히 더럽고, 길어졌습니다.

다른 방식의 문제 풀이 step 1

  • 정렬 후 이진 탐색을 진행합니다. 허나 범위를 이등분하는 조건과 mid 값을 처리하는 부분이 다릅니다.
  • 조건은 집 사이의 거리가 mid 값보다 클 때만 공유기를 설치합니다. 그리고 마지막 집까지 순회를 다 돌았을 때 설치한 공유기의 개수가 주어진 공유기의 개수보다 큰지 또는 같거나 작은지를 비교합니다.

소스코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const check = (arr, N, key) => {
	let cnt = 1;
	let before = arr[0];
	for (let i = 1; i < N; i++) {
		if (arr[i] - before < key) continue;

		cnt++;
		before = arr[i];
	}

	return cnt;
};

const solution = (input) => {
	let [N, C] = input[0].split(" ").map(Number);
	const arr = input
		.slice(1, N + 1)
		.map(Number)
		.sort((a, b) => a - b);

	let res = 1;
	let low = 1;
	let high = parseInt((arr[N - 1] - arr[0]) / (C - 1));
	while (low <= high) {
		let mid = parseInt((low + high) / 2);

		if (check(arr, N, mid) >= C) {
			res = mid;
			low = mid + 1;
		} else high = mid - 1;
	}

	return res;
};

console.log(solution(input));

후기

  • 굳이 첫 집과 마지막 집에 설치한다는 생각으로 접근할 필요가 없었습니다. 그리고 그저 mid 값보다 같거나 클 때만 설치를 하면서 설치한 공유기의 개수를 세는 방식으로 조건 함수를 구현하니 훨씬 간결하고 깔끔해졌습니다.
  • 사실 이렇게 하는 방식이 왜 맞는지에 대한 의문을 가지고 있었습니다. 아무리 생각해도 mid 값으로 설치를 하고 설치한 거리들을 다 수집해서 거기서 최소값을 찾아야 정답을 구할 수 있을 것 같은데, 최소값을 찾는 과정이 없어도 정답이 도출되었습니다.
  • 제 생각으로는 이진 탐색을 하면서 조건 함수에 적합한 최대 값을 찾는 방식으로 흐름이 진행되기 때문인 것 같습니다.
  • 즉, 우리가 공유기를 설치할 때 두 집의 거리가 mid 값보다 클 때만 설치를 진행합니다. 그렇기 때문에 혹여나 mid 값보다 작은 거리는 생길 수 없습니다. 또한 주어진 공유기보다 같거나 크면 mid 값을 증가시키기 때문에 mid값이 최대가 될떄까지 만듭니다. 또한 그 과정중 주어진 공유기의 개수와 같은 경우에 도달하기 때문에 별도의 최소값을 찾는 과정이 없어도 정답이 도출되는 것 같습니다.