[백준 2110번][Java] 공유기 설치 - 이분 탐색/중복된 요소 처리

 

www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

해결하는데 굉장히 오래 걸렸습니다.

계속 분할 정복 방식으로 구간을 나눠 최적의 공유기 위치를 설치하려는 방식으로 접근했기 때문인데, 

이 방식은 가능함의 여부를 떠나서(아마도 시간 제한에 걸릴 듯) 문제가 굉장히 복잡해지게 합니다.

 

관점을 살짝 바꿔야 합니다. 실제 수직선 위의 구간을 나눠가면서 공유기를 설치하는게 아니라, 최적화할 값들의 범위의 구간을 나눠가면서 정답을 찾아내야 합니다. 

 

이 문제의 경우 숨은 문제가 하나 더 있습니다. 단순히 이분 탐색을 구현하더라도 답을 찾지 못하는 경우가 생깁니다.

(인터넷의 많은 풀이들이 거의 같은 방식을 이용하기 때문에 자세한 이야기는 다른 사이트를 참고해주세용.)

이는 mid 값을 이용해서 공유기의 개수를 판정하는 로직으로 인해 생기는 문제입니다. 

mid 값보다 크거나 같은 거리의 정점에 공유기를 설치하기 때문에 가장 인접한 정점 간의 최소 거리 역시 mid보다 크거나 같을 수 있습니다. 

 

가장 인접한 정점 간의 최소 거리 중 최대를 찾으려면 같은 값들 중 가장 오른쪽에 위치한 값을 찾아야 합니다.

이는 이분 탐색의 조건을 같은 값이 나왔을 때 오른쪽 범위를 선택하게 함으로서 구현 가능합니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

/*
공유기 설치
https://www.acmicpc.net/problem/2110
 */
public class Main {
    static int N,C;
    static List<Long> house = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        InputReader reader = new InputReader();
//        InputReader reader = new InputReader("testcase.txt");
        StringTokenizer st = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            house.add(reader.readLong());
        }
        house.sort(Comparator.naturalOrder());

        long ret = findOptimizedMinimumGap(1, house.get(house.size()-1) - house.get(0), C);
        System.out.println(ret);
    }

    private static long findOptimizedMinimumGap(long low, long high, int targetRouterCnt) {
        long mid = (low + high)/2;
        if(low > high) return mid;

        int routerCnt = installRouter(mid);

        if(routerCnt < targetRouterCnt) {
            return findOptimizedMinimumGap(low, mid-1, targetRouterCnt);
        }else {
            return findOptimizedMinimumGap(mid+1, high, targetRouterCnt);
        }
    }

    /*
    정해진 간격을 기준으로 공유기를 설치한다. 해당 거리에 공유기가 없는 경우
    거리가 더 먼 집을 선택한다.
     */
    public static int installRouter(long gap) {
        int routerCount = 1;
        long startHouse = house.get(0);
        for (int i = 1; i < house.size(); i++) {
            long distance = house.get(i) - startHouse;
            if(distance >= gap) {
                routerCount++;
                startHouse = house.get(i);
            }
        }
        return routerCount;
    }
}

class InputReader {
    private BufferedReader br;

    public InputReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public InputReader(String filepath) {
        try {
            br = new BufferedReader(new FileReader(filepath));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    public List<Character> readLineIntoCharList() throws IOException {
        List<Character> l = new ArrayList<>();
        while(true) {
            int readVal = br.read();
            if(readVal == '\n' || readVal == -1) break;
            l.add((char)readVal);
        }
        return l;
    }

    public boolean ready() throws IOException {
        return br.ready();
    }

    public String readLine() throws IOException {
        return br.readLine();
    }
    public int readInt() throws IOException {
        return Integer.parseInt(readLine());
    }
    public Long readLong() throws IOException {
        return Long.parseLong(readLine());
    }
}