백준 공유기 설치 2110 js

문제링크

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

2110번: 공유기 설치

내가 푼 틀린 코드

const fs = require("fs");

const filepath =
  process.platform === "linux" ? "dev/stdin" : "./이분탐색/2110/input.txt";

const input = fs.readFileSync(filepath).toString().trim().split("\n");

const [A, B] = input.shift().split(" ").map(Number);

let ary = input.map(Number).sort((a, b) => a - b);

let answer = [];

function binary(ary, target) {
  let start = 0;
  let end = ary.length - 1;

  let short = 0;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);

    let startMid = ary[mid] - ary[start];
    let endMid = ary[end] - ary[mid];

    if (startMid < endMid) {
      end = end - 1;
    } else {
      start = start + 1;
    }

    short = Math.min(startMid, endMid);
    answer.push(short);
  }
}

binary(ary, B);

console.log(Math.max(...answer));

틀린 내 로직

 

이분탐색이.. 말이 탐색이지 탐색이 아닌거 같다. 이분탐색으로 근사 값 추려내서 그 근처에서 찾아내는 그냥 일종에 도구인거같다.

그래서 이분탐색으로만 끝내려고하면 안되는 것 같고 생각 자체를 좀 단순히 이분탐색만해야한다는 생각에서 바꿔야하는 것 같다..

 

• 이분탐색으로 start - mid 사이의 값, mid 와 end 사이의 값을 구했다.
• 두 값 중에 더 큰 값이 있으면 마치 투포인트 처럼 포인터를 -1 또는 +1 해주었다.
• start-mid 한 값과 mid -end 한 값에 작은 값을 빈 배열에 푸쉬해주었다.
• 배열에 들어 온 값들은 가장 근접한 값들이다. 여기 중에서 다시 가장 큰 값을 찾으면 됬다.

테케는 통과했지만 4%에서 자꾸 틀리길래 인풋 값을 여러번 다르게 줘봤는데 원하는 값이 나오지 않았다.

어떻게 좌우를 움직여야하는지 고민을 많이 했는데 결국 로직이 틀린 문제였다.

 

정답코드

const fs = require("fs");

const filepath =
  process.platform === "linux" ? "dev/stdin" : "./이분탐색/2110/input.txt";

const input = fs.readFileSync(filepath).toString().trim().split("\n");

const [A, B] = input.shift().split(" ").map(Number);

let ary = input.map(Number).sort((a, b) => a - b);

function count(ary, mid) {
  let endPosition = ary[0];
  let cnt = 1;

  for (let i = 0; i < ary.length; i++) {
    if (ary[i] - endPosition >= mid) {
      cnt++;
      endPosition = ary[i];
    }
  }

  return cnt;
}

function binary(ary, B) {
  let answer = 0;
  let start = 1;
  let end = ary[ary.length - 1];

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);

    if (count(ary, mid) >= B) {
      answer = mid;
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return answer;
}

console.log(binary(ary, B));

로직설명

처음에 로직이 이해가 안되서 노트에 적으면서 이해를 했다.

 

// 배열 [1,2,4,8,9]

• start 와 end 값을 평균 낸다. mid = 1 + 9 / 2  = 5
• mid 값을 count 함수로 넘겨준다.
• count 함수에서 하는 일은 길이를 측정해서 카운팅을 해준다.
• endPosition 으로 ary[0]인 1을 가지고 반복문을 돌리는데 ary[i] (1) - endPostion (1) >= 아까 mid 값 5 보다 크면 카운팅을 해주고 endPostioin 도 ary[i]로 치환해준다.
• 이게 무슨 의미이냐면 내 mid 보다 큰 값이 나타나면 거기를 endPostiion 으로 중간지점을 찍고 다시 ary[i] 와 거리계산을 한다는 것
• 예를들어서 endPostiion 이 1이고 ary[1] 이면 mid 5 보다 작으므로 다음 순으로 넘어가고 ary[3]일때 8인데 8-1 = 7 이기때문에 cunt ++ 이 되고 ary[3]의 8이 endpotisition이 되서 거점이된다. endposition은 8이 되고 다음 ary[4]이 9인데 9 -8은 1 이라서 5보다 작으므로 여기서 멈추게 된다.
• 다시 return count 는 아까 count 한 값 +1 이라 2를 반환하는데 2는 B 보다 작으므로 end 가 mid-1이 된다. end 는 아까 평균 낸 5 -1 이므로 4가 되고
• 다시 카운트 함수에 들어가서 ary[1] (1) - endposition (1) >=4 ~~~~ 이런식의 로직구현이다.