[백준-11497] 통나무 건너뛰기 | node.js | silver1

문제

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

11497번: 통나무 건너뛰기

 

풀이

function solve(n, tree) {
  tree.sort((a, b) => a - b);
  let maxLen = 0;
  for (let i = 2; i < n; i++) {
    maxLen = Math.max(maxLen, Math.abs(tree[i] - tree[i - 2]));
  }
  return maxLen;
}

const filePath =
  process.platform === "linux"
    ? "/dev/stdin"
    : "백준/silver/11497/testcase.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");
for (let i = 1; i < input.length - 1; ) {
  const n = +input[i];
  const tree = input[i + 1].split(" ").map((el) => +el);
  i += 2;
  console.log(solve(n, tree));
}

이 문제는 예를 들어서 설명해보겠다.

1, 3, 5, 7, 9, 12, 14, 16, 18, 20

다음과 같이 있다고 가정했을 때, 아래와 같이 배치 했을 때 난이도의 최소값이 나오게 된다. 이때 난이도는 5가 된다. 

1, 5, 9, 14, 18, 20, 16, 12, 7,  3

주어진 배열을 오름차순으로 정렬한 뒤 순서대로 양끝에 배치시킨 것이다. 그 이유는 1, 2 , 3, 100, 101, •••를 예로 들어서 설명하겠다. 3과 100을 인접시켜야만 난이도의 최소값이 나올 것 같지만 그렇지 않다. 3과 100을 인접시킬 경우,

만약, 3의 왼쪽에 1이나 2중 하나가 나온다면 그 1이나 2는 100보다 큰 어떤 값들과 인접될 수 밖에 없을 것이다. 그렇다면 3과 100의 차이보다 더 큰 차이값이 나오게 되므로 난이도의 최소값을 올바르게 도출할 수 없다.

만약, 3의 왼쪽에 100보다 큰 값이 인접하게 된다면 3과 100의 차이보다 3과 왼쪽에 인접한 그 값과의 차이가 더 커지기 때문에 3과 100이 최대 난이도가 아니게 된다. 따라서 오름차순된 배열을 작은 값부터 양 끝에서부터 번갈아가며 배치해야 한다.

1 => 1, 3 => 1, 5, 3 => 1, 5, 7, 3 => ••• => 1, 5, 9, 14, 18, 20, 16, 12, 7, 3

 결국, 통나무를 오름차순으로 정렬한 뒤 i번째 값과 i-2번째 값을 비교한 것과 같은 로직이다. 
1, 3, 5, 7, •••  => 1과 5비교, 3과 7비교, •••