[JAVA]BOJ 2110, 공유기 설치

이진탐색 문제 왤케 어렵지.. 연속해서 풀어도 감 잡기가 힘들다.

 

집에다가 공유기를 C개 설치하는데, 설치된 집 사이 거리들 중, 거리가 좁은 쪽을 구한다. 좁은 쪽의 거리들 중에 최댓값을 찾는다. 아래는 예시이다.

*은 공유기이다. 설치를할때.. 

 1 2   4        8 9  -> 이런식으로 하면 최소거리는 1이다(1~2)
  * *   *

 1 2   4        8 9  -> 최소거리는 3(1~4)
  *      *         *

 1 2   4        8 9  -> 최소거리는 3(1~4)
  *      *           *

 1 2   4        8 9  -> 최소거리는 1(8~9)
  *                * *

이 중 제일 큰 최소거리인 3(1~4)가 답이다!

 

뭘 탐색해야되나..? 사실 풀때까지만 해도 헷갈렸는데.. 최소거리를 탐색하면 된다. 이진탐색을 쓰지않더라도 답은 나온다. 시간초과가 나와서 그렇지.. 최소거리가 1일때, 2일때, 3일때 ... houses[N-1] - house[0] 까지 하나하나 탐색하면 된다.

houses[N-1] - house[0]는 제일 큰 최소거리이다. 위 예시에서 공유기를 양 끝에 설치하는게 제일 멀리 설치하는거니까.. 그 거리는 9 - 1 = 8이다. 그래서 이진탐색은 1부터 houses[N-1] - house[0]의 범위에서 실행한다. 

 

공유기 설치 함수, 이진탐색 함수, main 이렇게 3개로 나눴다. 

 

1. 공유기 설치

public static int checkRouter(int[] houses, int distance, int C){
    int cnt = 1, lastInstalled = houses[0], i = 1; // house[0]에는 이미 설치함

    for(i=1;i<houses.length;i++){
        if(houses[i] - lastInstalled >= distance){
            lastInstalled = houses[i];
            cnt++;
        }
        if(cnt == C)
            return 1;
    }

    return 0;
}

 

distance는 최소거리이다. 최소거리들 중 큰 값이 답이 되고 여기서는 최소거리로 설치할 수 있냐? 를 확인한다. 

house[i]는 설치 할 수 있는지 확인할 집이고, lastInstalled는 마지막에 설치된 공유기의 위치이다. lastInstalled = house[0]는 처음 집에 공유기를 설치했다는 뜻이고, 1개를 설치했으니 cnt(설치한 개수)를 1로 초기화한다.

house[i] - lastInstalled를 한 값이  distance보다 크거나 같아야 설치가 가능하고 조건을 주었다. 맞는 경우에는 house[i]에 공유기를 설치하고, cnt를 증가시킨다.

만약 이렇게 계속 설치하다가 설치해야할 개수(C)와 설치한 개수(cnt)가 같아지면 distance보다 크거나같은 위치에 모든 공유기를 설치한 것이므로 1을 반환한다. 아니면 설치를 다 못한것이니 0을 반환한다.

 

2. 이진탐색(반복문)

public static int binarySearchLoop(int[] houses, int C){
    int low = 1, high = houses[houses.length - 1] - houses[0], mid, ans = 0;

    while(low <= high){
        mid = (low + high) / 2;
        if(checkRouter(houses, mid, C) == 1){
            ans = mid;
            low = mid + 1;
        }
        else
            high = mid - 1;
    }

    return ans;
}

앞서 말한대로 low와 high를 알맞게 정의한다. mid는 공유기를 설치할때(checkRouter) distance가 된다. 설치가 가능한 경우 조금 더 큰 mid(distance)가 있을 수도 있으니 오른쪽으로 이진탐색을 진행한다.

설치가 불가능한 경우, 더 좁은 mid(distance)로 설치하기위해 high = mid - 1로 지정해 왼쪽 이진탐색을 한다.

---

아래는 전체 코드이다.

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

public class BOJ2110 {
    public static int checkRouter(int[] houses, int distance, int C){
        int cnt = 1, lastInstalled = houses[0], i = 1; // house[0]에는 이미 설치함

        for(i=1;i<houses.length;i++){
            if(houses[i] - lastInstalled >= distance){
                lastInstalled = houses[i];
                cnt++;
            }
            if(cnt == C)
                return 1;
        }

        return 0;
    }

    public static int binarySearchLoop(int[] houses, int C){
        int low = 1, high = houses[houses.length - 1] - houses[0], mid, ans = 0;

        while(low <= high){
            mid = (low + high) / 2;
            if(checkRouter(houses, mid, C) == 1){
                ans = mid;
                low = mid + 1;
            }
            else
                high = mid - 1;
        }

        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, C, i;
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        int[] houses = new int[N];

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

        Arrays.sort(houses);

        System.out.println(binarySearchLoop(houses, C));
    }

}

반례 및 코드 돌아가는 예시..

 

5 3

1

2

4

8

9

답: 3

low = 1, high = 8, mid = 4 / 1 2 3 *4 5 6 7 8

<checkRoute함수>
1 2 4 8 9
*     *   -> 안됨 -> high = mid - 1

low = 1, high = 3, mid = 2 / 1 *2 3

<checkroute함수>
1 2 4 8 9
*   * *   -> 됨 -> 되는데 최댓값 찾아야하니 조금 더 큰걸로 해도 되는지 확인하기 -> low = mid + 1

low = 3, high = 3 , mid = 3 / *3

<checkroute함수>
1 2 4 8 9
*   * *  -> 됨 -> 더 큰 값 있는지 찾기 -> low = mid + 1

low = 4, high = 3 -> 끝남


5 4
1
3
5
10
11
답: 2

  1   3   5         10 11  -> mid는 공유기 설치시 최소 거리를 뜻함, 이진탐색 범위: 1~([n-1]-[0]), 공유기를 놓을 수 있는 최소~최대거리
  *   *   *          *

  1   3   5         10 11  ->  low = 1, high = 10, mid = 5 -> F리턴
  *                  *

  1   3   5         10 11  -> low = 1, high = 4, mid = 2
  *

  1   3   5         10 11  -> low = 1, high = 4, mid = 2 -> T리턴
  *   *   *          *