안테나

문제

백준 18310번 - 안테나

언어

JavaScript

순서도

마을 위치 정렬하기
첫 번째 도시에서 다른 모든 도시와의 거리 모두 구하기
두 번째 도시부터 하나씩 검사하며, 거리가 최소인 도시 찾기

문제 풀이 step 1

일직선 상의 마을에 여러 채의 집이 위치해 있습니다.
이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했습니다.
효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 합니다.
이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일할 위치에 여러 개의 집이 존재하는 것이 가능합니다.
집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 문제입니다.

문제 풀이 step 2

그리디 알고리즘을 적용하는 문제로, 매 상황에서 최적의 선택을 하는 방식을 이용합니다.
우선 주어진 도시들의 위치를 오름차순으로 정렬합니다.
그리고 모든 도시에서 한 도시씩 선택해가며, 선택한 도시를 제외한 모든 다른 도시와의 거리를 구합니다.
이 때, 주어지는 집의 수의 최대가 200,000 이라서, 각 도시를 검사할 때 마다 매번 모든 도시와의 거리 차이를 구하면 시간초과가 발생합니다.
- 따라서, 첫 번째 도시에서 모든 도시와의 거리를 구해놓고, 다음 도시와의 거리값을 활용해서 반복되는 불필요한 연산을 피해줍니다.
모든 도시를 검사하고, 그 중에서 거리값이 최소가 되는 도시 번호를 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

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

	let ans = arr[0];
	let min = 0;
	// 첫 번째 도시와 모든 도시와의 거리 구하기
	for (let i = 1; i < n; i++) {
		min += arr[i] - arr[0];
	}

	// 다음 도시부터 모든 도시와의 거리 구하기
	for (let i = 1; i < n; i++) {
		// 다음 도시와의 거리 구하고,
		const diff = arr[i] - arr[i - 1];
		// 이를 이용해서 다른 도시와의 거리 차이 구하기
		const sum = min + diff * i - diff * (n - i);

		// 거리가 최소인 경우 찾기
		if (min > sum) {
			min = sum;
			ans = arr[i];
		}
	}

	return ans;
};

console.log(solution(input));