문제 탐색하기

입력 자료 정리

1. n은 집의 개수, c는 공유기의 개수다
2. 이후 n만큼 들어오는 입력값은 각 집의 좌표 값이다.

해결방법 추론

1. 집의 좌표값 최대가 10^9이며, n과 c도 최대 20만이다.
   따라서 일반적인 탐색이나 조합으로는 해결할 수 없다
2. 범위가 클때는 보통 이분탐색을 떠올리면 해결방법이 된다
3. 이분탐색할 기준을 찾아야 하는데, 범위가 큰 좌표를 기준으로 했다
4. 이분탐색 대상을 어떻게하면 정답을 찾는 도구로 사용할 수 있을지 고민했다
5. 오름차순된 집간의 거리가 이분탐색하는 범위 이상이라면,
   해당 집에는 공유기를 설치할 수 있을 것이다
6. 만약 공유기를 설치할 수 있다면 c의 값에 상관없이 개수를 세어준다
7. 그리고 이 개수를 가지고 이분탐색을 한다면,
   정답을 만족하면서 가장 인접한 두 공유기 사이의 최대 거리를 얻게될 것이다

시간복잡도 계산

1. 이분탐색 과정에서 logXi의 연산이 발생하고,
   이 과정에서 모든 집을 탐색하므로 n의 연산이 발생할 것이다
2. 종합하면 시간복잡도는 O(n x logXi)가 될 것이며,
   시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. 크기는 변수에서 관리하며, 집의 좌표는 int형 1차원 배열로 관리한다
2. 이분탐색을 위해 배열은 오름차순 정렬한다
3. left와 right는 각각 Xi의 최소,최대로 지정해주며, ans는 0으로 초기화한다

구현 코드 설계

1. 이분탐색 과정은 초기화 - 탐색 - 최적화
2. 초기화 과정에서는 mid값을 얻고, 이전값과의 비교를 위해 첫번째 위치의 값을 변수로 가진다
3. 설치된 개수를 세기 위해 count 변수를 선언하는데,
   어떠한 간격이라도 첫 설치지점은 설치할 수 있기 때문에 1로 초기화한다
4. 검증 과정에서는 이전 값과 비교하며, mid보다 작은 경우 건너뛰고 아닌 경우 개수를 세어준다
   또한 이전 값에 대해 현재 값으로 갱신해준다
5. 이분탐색 결과 설치 가능한 개수가 c보다 작으면 정답을 만족하지 못하므로 right 범위를 조절한다
6. 아닐 경우, left 범위를 조절하며 최적의 경우를 찾고 ans를 mid로 갱신한다

출력값 설계

1. 완성한 ans를 출력하면 정답이 된다.

추가 테스트케이스

테스트케이스 1

입력

5 5
1
2
3
4
5

결과

• 예상 출력값: 1

테스트케이스 2

입력

6 4
6
8
14
16
29
3000

결과

• 예상 출력값: 10

테스트케이스 3

입력

1
1000000
1000100
1100100
110010010
111111111
1000000000

결과

• 예상 출력값: 1100099

참고: 999999 1000099 1100099 110010009 111111110 999999999 [집 위치간 간격]

정답 코드

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

public class Main {

    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());
        int n = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        int left = 0;
        int right = 1_000_000_000;
        int ans = 0;
        while(left <= right){
            int mid = (left + right) / 2;
            int last = arr[0];
            int count = 1;
            for (int i = 1; i < n; i++) {
                if(arr[i] - last < mid){
                    continue;
                }
                count++;
                last = arr[i];
            }

            if(count < c){
                right = mid - 1;
            }else{
                left = mid +1;
                ans = mid;
            }
        }

        bw.write(ans+"");

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

문제 링크

2110번 - 공유기 설치