[골드4] 백준 2110번 '공유기 설치' (이분탐색)

mid를 중심으로 좌우 탐색을 반복하는 건 알겠으나 실제 구현이 막힌다면 아마도 참고할 만한 글

이분탐색 문제 특징

• 탐색해야 할 값이 엄청 크다 (ex. 1,000,000,000)
• 최대, 최소를 묻는다

공유기 설치 문제 바로가기

어떻게 접근할까?

'탐색할 값' 과 '탐색할 범위' 이렇게 2개를 정해야 한다.
그리고 이분 탐색 로직을 생각한다.
※ 정렬, 타입(long)

1. '탐색할 값(mid)' 정하기
   • 뭘 구하라는지 문장을 살핀다
     • ex. 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
       → 가장 인접한 두 공유기 사이의 거리를 값(mid)으로 둔다.
2. '탐색할 범위(left, right)' 정하기
   • 언제 이 값이 최소, 최대가 될 지 생각한다.
     • ex. 인접한 두 공유기 사이 최소, 최대 거리는 설치가 가장 가까이 됐을 때, 가장 멀리 됐을 때이다. 가장 가까운 건 1, 가장 먼건 처음 집에서 마지막집 사이 거리.
     • 이때 left, right 타입 중요함. int로 처리가 안될 수 있으니 long도 고려할 것
3. 이분 탐색 코드 구현
   1. 값을 구하는데 필요한 데이터를 정렬한다.
      • ex. 집 좌표 정렬
   2. 이 값(mid)이 정답이라고 가정했을 때 조건에 맞게 처리할 방법을 생각한다.
      • ex. 가장 인접한 거리가 mid라면, 이 mid보다 큰 거리로 공유기를 설치할 수 없을 것이다. 그랬을 때 공유기를 몇 개 설치할 수 있는지 반복문을 돌며 계산한다.
   3. 처리된 결과에 따라 mid를 작게 혹은 크게 만들건데, 이때 비교연산자 (==) 는 어느 조건에 붙여야 하고 정답을 어느 조건에서 갱신할 지 생각한다.
      • ex. 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
        → 최대를 구해야 하므로 mid가 커지는 조건문(left = mid+1 가 포함된 곳)에 등호와 정답 갱신이 필요하다. (만약 최소를 구한다면 mid가 작아지는 조건문에 등호와 정답 갱신 필요) - 이건 직접 시뮬레이션해서 확인 한번 더 해보면 좋을듯

정답 코드

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

/*
9:48 ~ 10:28
1. 집 정렬
2. 탐색할 값 : 공유기 사이 거리 최대값
탐색 범위: 공유기 사이 거리 최소, 최대
최소: 1
최대: 가장 큰 집 - 가장 작은 집 = 9 - 1 = 8

가장 인접한 공유기 사이 거리가 d라면
d보다 더 작은 거리가 생기면 안됨

mid: 2
D:  1 2 4 1
H: 1 2 4 8 9
   .   . . 

*/
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int C = sc.nextInt();
        long[] homes = new long[N];
        for(int i = 0; i < N; i++) {
            homes[i] = sc.nextLong();
        }
        
        Arrays.sort(homes);
        long answer = 0;
        long left = 1;
        long right = homes[N-1] - homes[0];
        while(left <= right) {
            long mid = (left + right) / 2;
            
            int cCnt = 1; // 공유기 설치 개수
            int cIdx = 0; // 공유기가 마지막으로 설치된 인덱스 
            for(int i = 1; i < N; i++) {
                long d = homes[i] - homes[cIdx];
                if(d >= mid) { // 공유기 설치
                    cIdx = i;
                    cCnt++;  
                }
            }
            
            if(cCnt >= C) {  // mid 키움
                left = mid + 1;
                answer = mid;
            } else { // mid 줄임
                right = mid - 1;
            }
        }
        
        System.out.print(answer);
        sc.close();
    }
}

시간 복잡도는 얼마일까?

• 정렬: O(NlogN)
• 이분탐색: O(NlogD)
  • D는 mid 탐색 범위. 즉 집 최대 거리차 (D=homes[N-1] - homes[0])

따라서 O(NlogN+NlogD) 가 최종 시간 복잡도이다.