Programmersマット

6525 ワード
JavaScript algorithm テキストリンク

中に入る。


この問題のパターンを一度見た.白俊のルーター設定の問題とよく似ています.以前やっていた時も解けなかったようですが、やはり疲れました.答えを見るのも難しい質問この探索の核心は文章に整理された.

解説


この探索の核心は、まず答えを確定し、それから答えが正しいかどうかを見つけることだ.
  • 最初の答えは、開始から終了までの中間点です.
  • の値が正しいことを確認します.
  • の予測答えを上回ると、上に減少し、下に下がると、下に上昇します.
  • 石は起点から最初の石まで位置を確認します.だからfor文の冒頭は1です.
  • count>nは、正しい値を返す必要があります.

    • 質問する


    https://programmers.co.kr/learn/courses/30/lessons/43236 
    function solution(distance, rocks, n) {
  rocks = [0, ...rocks.sort((a, b) => a - b), distance];
  let left = 0,
    right = distance;

  while (left <= right) {
    let mid = Math.floor((right + left) / 2),
      count = 0,
      now = 0;

    // * 이분탐색 실행
    // ! 1부터 시작해야 0번 돌과 1번 돌의 거리를 계산할 수 있음
    for (let i = 1; i < rocks.length; i++) {
      if (rocks[i] - now < mid) {
        count++;
      } else {
        now = rocks[i];
      }
    }
    // * 이분탐색 판별
    if (count > n) right = mid - 1;
    else left = mid + 1;
  }

  return right;
}

console.log(solution(25, [2, 14, 11, 21, 17], 2));

    参考資料


    https://gwang920.github.io/algorithm/progreammers-2-43236/
    https://velog.io/@injoon 2019/アルゴリズム-伯準-2110-ルータ-インストール
    バイドゥ
    [パイソン]白準11729ハノイタワー移動順