백준 2110번 : 공유기 설치 (Java)

🔗 문제 링크

2110번: 공유기 설치

---

📖 풀이 과정

- 이분탐색 유형의 문제입니다.

- 메소드를 분리하면, binarySearch() 메소드는 적절한 거리 길이를 구하는 메소드, canInstall() 메소드는 집의 개수를 세는 메소드입니다.

- binarySearch() 메소드 내부를 보면, 이분탐색의 알고리즘을 적용합니다. 
  - 입력받은 c 변수와 비교하여 변수 answer에 담아 반환합니다.
  
- canInstall() 메소드 내부를 보겠습니다.
  - count 변수는 1로 초기화 합니다. 그 이유는, 해당 인덱스의 집은 공유기를 설치한다고 판단하기 때문입니다.
  - 마지막으로 공유기 설치한 집에 대한 변수, 이제 설치한 집에 대한 변수와 거리 차이를 통해 dist 변수와 비교하여 count 값을 변경합니다.
  - 최종적으로 몇 개의 집인지 반환합니다.

---

💻 코드

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    static int n,c;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        bw.write(binarySearch(1, arr[arr.length - 1]));
        bw.flush();

        bw.close();
        br.close();
    }

    private static String binarySearch(int start, int end){
        int answer = 0;
        while(start <= end){
            int mid = (start + end) / 2;

            if(canInstall(mid) < c){
                end = mid - 1;
            }else{
                answer = mid;
                start = mid + 1;
            }
        }
        return String.valueOf(answer);
    }

    private static int canInstall(int dist){
        int count = 1; // 시작 집은 무조건 설치
        int lastInstall = arr[0];

        for(int i = 1; i< arr.length; i++){
            int toLocate = arr[i];

            if(toLocate - lastInstall >= dist){
                count += 1;
                lastInstall = toLocate;
            }
        }

        return count;
    }
}