[BOJ] 2110번 공유기 설치 - JAVA(자바)

2110번: 공유기 설치

💡 이진탐색(Binary Search) 문제

구하고자 하는 것 : 두 공유기 사이의 최대거리

lt = 1

rt = arr[n-1] ➜ 너무 세세하게 생각X. 그냥 가장 멀리있는 좌표 선택

➜ 답(두 공유기의 최대거리)은 lt~rt 사이에 확실하게 있다.

 

mid = (lt + rt ) / 2 

 

가장 인접한 두 공유기의 거리를 mid라고 했을 때, 답이 가능한지 검증 ➜ 공유기의 배치 수를 count하는 함수 생성

• 검증 성공 시, 최대 거리를 구해야 하므로 오른쪽 부분에서 찾기 lt=mid+1
• 검증 실패 시, 왼쪽 부분에서 찾기 rt=mid-1

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

class Main {
    public int count(int[] arr, int dist) {
        int cnt = 1;
        int ep = arr[0]; // 공유기는 시작점에 배치
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] - ep >= dist) {
                // 정한 최대거리(mid)보다 크거나 같으면 공유기 배치
                cnt++;
                ep = arr[i];
            }
        }
        return cnt;
    }

    public long solution(int c, int[] arr) {
        Arrays.sort(arr); // 배열 정렬
        int answer = 0;
        int lt = 1;
        int rt = arr[arr.length-1];

        while (lt <= rt) {
            int mid = (lt + rt) / 2;

            // c 개 보다 공유기를 더 많이 놓을 수 있다면 거리를 넓혀야됨.
            if (count(arr, mid) >= c) {
                answer = mid;
                lt = mid + 1;
            } else rt = mid - 1;
        }

        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner s = new Scanner(System.in);

        int n = s.nextInt();
        int c = s.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextInt();
        }

        System.out.println(T.solution(c,arr));

    }
}

 

---

[JAVA/알고리즘] 이진 탐색 알고리즘을 이용한 문제해결