문제 개요

문제: 센서

분류: 그리디 알고리즘, 정렬

난이도: 골드5

문제 풀이

우선 밀접해 있는 센서들 간의 거리를 구해야 한다.

• 이를 위해 입력 받은 센서들의 위치를 오름차순 정렬한다.
• 정렬 후 밀접한 두 센서 간의 거리를 구한다.

그 후 가까운 센서들을 묶어서 각 묶음 당 하나의 집중국을 세워야 한다.

• 수신 가능 영역의 길이를 최소화해야 하므로 위에서 구한 밀접한 센서들 간의 거리를 오름차순 정렬한다.
• 집중국의 개수가 K개일 때 수신 받아야 하는 개수는 센서의 개수 N에서 K만큼을 뺀 것이다.
  따라서 정렬한 거리의 상위 N-K개를 더한 것이 정답이 된다.

아래는 문제에서 주어진 예제 입력 2의 정렬 결과를 그림으로 표현한 것이다.

• 3에 설치 → 수신 가능 영역 길이 0
• 6~8 사이에 설치 → 수신 가능 영역 길이 1+1=2
• 10~15 사이에 설치 → 수신 가능 영역 길이 2+2+1=5
• 18에 설치 → 수신 가능 영역 길이 0
• 20에 설치 → 수신 가능 영역 길이 0

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const solution = (input) => {
  const N = +input[0]; // 센서의 개수
  const K = +input[1]; // 집중국의 개수
  const sensor = input[2].split(" ").map(Number);
  const dist = [];

  // 센서 좌표를 오름차순으로 정렬한다.
  sensor.sort((a, b) => a - b);

  // 밀접한 두 센서 사이의 거리들을 구한다.
  for (let i = 0; i < N - 1; i++) dist.push(sensor[i + 1] - sensor[i]);

  // 수신 가능 영역의 길이의 합을 최소화해야 하므로 거리를 오름차순 정렬한다.
  dist.sort((a, b) => a - b);

  // 수신 받아야 하는 개수 = 센서의 개수 - 집중국의 개수
  // 정렬한 거리의 상위 N-K개의 합이 정답이 된다.
  let answer = dist.slice(0, N - K).reduce((prev, curr) => prev + curr, 0);
  console.log(answer);
};

solution(input);