백준 2110 JAVA : 공유기설치

문제

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

2110번: 공유기 설치

 

풀이 예상

집의 좌표 범위가 10억을 넘으므로 이분탐색을 통해서 범위를 줄여가야겠다고 생각했다.

가장 인접한 공유기 거리를 구하고 그 거리로 집 배열을 탐색하면서 C개 이상 설치가 가능한지 여부를 파악한다.

 

풀이방법 (접근 방법 & 시간복잡도)

1. 집의 위치를 배열에 넣고 오름차순으로 정렬한다.

2. start = 1, end = house[N-1] - house[0] (제일 큰 차이) 로 두고 이분 탐색을 시작한다.

3. mid 값으로 공유기를 얼마나 설치할 수 있는지 카운트한다.

house 배열과 mid 값이 5인 경우

 

house[0]	house[1]	house[2]	house[3]	house[4]	house[5]
1	2	5	10	20	40

 

3-1. count = 1 (초깃 값, 처음 집은 무조건 설치), keep = 1(house[0])

3-2. i = 1

       house[1] - keep < mid(5) 이므로 아무일도 일어나지 않는다.

3-3. i = 2

       house[2] - keep < mid(5) 이므로 아무일도 일어나지 않는다.

3-4. i = 3

       house[3] - keep > mid(5) 이므로 count = 2, keep = house[3]갱신

3-5. i = 4

       house[4] - keep > mid(5) 이므로 count = 3, keep = house[4]갱신

3-6. i = 5

       house[5] - keep > mid(5) 이므로 count = 4, keep = house[5]갱신

4. count가 K보다 작다면 거리를 줄여야 하기 때문에 end값을 갱신하고, 그렇지 않다면 start값을 갱신한다.

 

 

시간복잡도 => O(N * log N)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        int[] house = new int[N];
        for (int i = 0; i < N; i++) {
            house[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(house);
        int start = 1;
        int end = house[N-1]-house[0];

        while(start <= end) {
            int mid = (start+end)/2;
            int count = 1; //house[0] 은 공유기 설치

            int keep = house[0];
            for (int i = 1; i < N; i++) {
                if(house[i] - keep >= mid) {
                    count++;
                    keep = house[i];
                }
            }

            if(count < C) {
                end = mid-1;
            }else {
                start = mid+1;
            }

        }
        System.out.println(end);

    }
}

 

결과