[JS] 백준 2110번 : 공유기 설치 - 이분 탐색

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

2110번: 공유기 설치

 

 

📋풀이방법

1. 이분탐색 문제이므로 lt와 rt변수를 선언한다.

-lt는 1로 초기화한다. -> lt는 각 집마다의 공유기설치 최소거리를 뜻한다.

-rt는 주어진 집의 좌표를 오름차순으로 정렬하고 가장 마지막 값으로 초기화한다. -> rt는 각 집마다의 공유기 설치 최대거리를 뜻한다.

2. while반복문으로 lt가 rt보다 작거나 같을 때까지 반복한다. -> 공유기 설치거리가 최대가 될 때까지 탐색해야한다.

3. 이분탐색에서 중요한 mid변수를 안에 선언한다.

-mid는 이분탐색에서 중요한 요소이다.

-mid는 lt+rt/2를 한 값이다, 즉 lt와 rt사이 가운데 값이다.

4. mid값은 최소거리 lt와 최대거리 rt의 절반 값이다.

5. 계속 반으로 나눠가면서 각 집마다의 공유기 최대거리를 찾는 것이다.

6. count함수를 따로만든다.

7. count함수에서는 공유기를 주어진 좌표에 공유기를 정해진 mid 거리만큼 띄워서 설치한다.

8.설치하면서 공유기를 카운팅한다.

9.만약 공유기를 C대이상 설치할 수 있다면 mid값을 더 크게 해야하는 것이므로 lt를 mid+1로 초기화한다.

-그리고 answer에 현재 mid값을 일단 기록한다

- 반복하면서 최적의 최대거리를 가장 나중에 저장하게 된다.

10. 만약 공유기를 C대 미만 설치할 수 있다면 mid값을 더 작게 해야하는 것이므로 rt값을 mid-1로 초기화한다.

 

 

📡

이해가 가지 않는다면 그림으로 살펴보자

 

1. 먼저 mid값을 구했다.

2.mid값 5로 현재 정한 공유기 사이 거리는 5다.

3. mid=5는 공유기를 2대밖에 설치하지 못하므로 정답이아니다.

4. mid값이 너무 큰 것이므로 mid값을 줄여야한다.

5. rt값을 mid-1로 해서 mid=(lt+rt)/2 에서 값을 줄인다.

-왜 mid-1로 하나요?

mid값인 5는 이미 위에서 검사했으므로 5라는 숫자는 제외해야한다.

6. mid값을 2로 공유기 사이 거리를 2로 정했을 때 검사해본다.

7. 3개 이상을 설치할 수 있게 됐으므로 정답이된다.

8.하지만 더 최대의 거리를 찾기위해서 반복을 계속해야한다.

9. lt값을 mid+1로 지정하고 mid=(3+4)/2를 통해 공유기 사이 거리를 다시 지정해서 검사해본다.

10. 3으로 지정해도 공유기 3개를 설치할 수 있으므로 정답이된다.

11. 하지만 더 최대의 거리를 찾기위해서 계속 반복해야한다.

12. lt값을 mid+1로 지정한다.

13. 그럼 lt는 4가 되고 rt도 4가된다. mid값은 8이 된다. lt와 rt가 같아지면 마지막 반복이라는 뜻이다.

14. 거리를 4로 정했을 때는 2개의 공유기를 설치하므로 정답이 되지 않는다.

15. 그러므로 정답은 이전에 검사했던 3이 정답이 된다.

 

🤟내 제출

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

let [N, C] = input[0].split(" ").map(Number);
let arr = [];
for (let i = 0; i < N; i++) {
  arr.push(Number(input[i + 1]));
}
arr.sort((a, b) => a - b);
let lt = 1;
let rt = arr[arr.length - 1];
let answer = 0;

let check = (house, dist) => {
  let cnt = 1;
  let ep = house[0];
  for (let i = 1; i < house.length; i++) {
    if (house[i] - ep >= dist) {
      cnt++;
      ep = house[i];
    }
  }
  return cnt;
};

while (lt <= rt) {
  let mid = parseInt((lt + rt) / 2);
  if (check(arr, mid) >= C) {
    answer = mid;
    lt = mid + 1;
  } else {
    rt = mid - 1;
  }
}
console.log(answer);

 

 

💢어려웠던 점

1. 이분탐색, 결정알고리즘을 다 까먹었다.

- 이분탐색문제를 다시한번 복기하는 좋은 문제였다.

2. check함수를 통해서 lt와 rt값을 정해야 되는데 이를 생각해내지 못했다.

-lt값과 rt값을 줄이거나 늘려가면서 mid값을 조정해 최적의 값을 찾는 것인데 이를 위한 검사하는 함수 check를 구현하는 과정에서 시간이 오래걸렸다.

- 1. 공유기를 첫번째 좌표에 무조건 설치한다.

- 2. endpoint라는 변수를 선언해서 가장 최근에 공유기를 설치했던 좌표를 기억해준다.

- 3. 주어진 집의 좌표를 차례로 순회하면서 endpoint값과 현재 순회하는 값의 차이가 mid값보다 크거나 같게 될 경우 정해진 mid값을 기준으로 공유기를 설치할 수 있으므로 현재 그 좌표에 공유기 설치 후 카운팅 +1 해준다.

- 4. 그리고 endpoint를 현재 좌표로 바꿔주고 계속해서 순회한다.

- 5. 모두 순회하고 카운팅된 값을 반환해줌으로써 mid값을 기준으로 공유기가 몇 대 설치됐는지 알 수 있다.