백준 2110 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

---

Python

from sys import stdin

n, c=map(int, stdin.readline().strip().split())
house=sorted([int(stdin.readline().strip()) for _ in range(n)])

start=1
end=(house[-1]-house[0])//(c-1)+1
answer=0

while start<end:
    mid=(start+end)//2

    current=house[0]
    count=0
    for i in house[1:]:
        if i-current>=mid:
            current=i
            count+=1

    if count<c-1:
        end=mid
    else:
        answer=mid
        start=mid+1

print(answer)

Java

import java.io.*;
import java.util.*;

public class Main {
    public static boolean check(int[] house, int n, int c){
        int count=1;
        int previous=house[0];
        for(int i=1; i<house.length; i++){
            if(house[i]-previous>=n){
                count++;
                previous=house[i];
                if(count==c)
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s=br.readLine();
        StringTokenizer st=new StringTokenizer(s);
        int n=Integer.parseInt(st.nextToken());
        int c=Integer.parseInt(st.nextToken());
        int[] house=new int[n];

        PriorityQueue<Integer> pq=new PriorityQueue<Integer>();
        for(int i=0; i<n; i++)
            pq.add(Integer.parseInt(br.readLine()));

        for(int i=0; i<n; i++)
            house[i]=pq.remove();

        int start=1;
        int end=(house[house.length-1]-house[0])/(c-1);

        while(start<end){
            int mid=1+(start+end)/2;
            if(check(house, mid, c))
                start=mid;
            else
                end=mid-1;
        }

        if(check(house, start, c))
            System.out.println(start);
        else
            System.out.println(end);
    }
}

---

해결 과정

1. 집의 좌표들을 받고 좌표 간의 거리를 Linked List에 저장했다. 좌표 간의 거리이기 때문에 Linked List의 크기는 집의 개수-1이고, LinkedList의 Iterator를 사용해서 Linear Search로 이웃한 두 거리의 합이 가장 작은 구간을 찾았다. 그리고 그 구간의 두 거리를 Linked List에서 remove 하고 두 거리의 합을 그 자리에 add 해줬다. 이렇게 되면 한 번 반복할 때마다 Linked List의 크기가 1씩 줄어들고 결국 공유기의 개수와 똑같아졌을 때, 원하는 답을 얻을 수 있다.

2. 시간 초과(매번 반복할 때마다 Linked List의 처음부터 끝까지 순회하고, 또 remove와 add를 할 때 처음부터 해당 인덱스까지 순회해야 하기 때문에 시간이 오래 걸린다)

3. 공유기 사이 거리의 최소:1, 최대:처음 집과 마지막 집의 거리차/공유기 개수 로 잡고, 그 중간의 mid 값보다 최소한 같거나 크도록 공유기를 설치해본 뒤, 총 설치된 공유기 수와 문제에서 주어진 공유기 수를 비교해서 최적의 거리를 Binary Search 했다.
   +받은 집의 좌표를 오름차순으로 정렬할 때, Arrays.sort() 대신 Priority Queue를 사용해서 정렬했다.

4. 반 년이 지나서 이번에는 파이썬으로 풀었는데 1시간 반이나 걸렸다...난 멍청하다

5. 😁