백준 11497 < 통나무 건너뛰기 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/11497

11497번: 통나무 건너뛰기

 

📍알고리즘 분류

- 그리디

- 정렬

 

📍문제 풀이

수열이 주어진다. 인접한 수 끼리의 차가 최소가 되도록 배열을 섞을 수 있을 때, 그 차를 구하라

 

예를 들어 정렬된 수열 10, 10, 11, 11, 12, 12, 13 이 주어질 때,

- 인덱스를 0 1 2 3 4 5 6 이라고 할 수 있다

 

오름차순으로 양 끝단부터 배치하게 되면 아래처럼 배치할 수 있다

(정렬된 배열이므로 크기가 정규 분포 모양이 될 것이다)

- 0 2 4 6 5 3 1

 

즉, 2 차이의 인덱스씩 비교하면 된다!

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
const output = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const N = +input.shift();
  for (let i = 0; i < 2 * N; i += 2) {
    const len = +input[i];
    const heightArr = input[i + 1]
      .split(" ")
      .map(Number)
      .sort((a, b) => a - b);
    let max = 0;
    for (let i = 0; i < len - 2; i++) {
      max = Math.max(max, Math.abs(heightArr[i] - heightArr[i + 2]));
    }
    output.push(max);
  }
  console.log(output.join("\n"));
});