https://www.acmicpc.net/problem/2110
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int numOfHouse= Integer.parseInt(st.nextToken());
int numOfWifi = Integer.parseInt(st.nextToken());
int[] house = new int[numOfHouse];
for (int i=0; i<numOfHouse; i++) {
house[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(house);
int result = 0; // 최종 답
int start = 1; // 현재 가능한 최소 이동거리
int end = house[numOfHouse-1] - house[0]; // 현재 이동가능한 최대 이동거리
while (start <= end) {
int midGap = (start+end)/2;
int value = house[0];
int count = 1;
for (int i=1; i<numOfHouse; i++) {
if (house[i] >= (value + midGap)) {
value = house[i];
count++;
}
}
if (count >= numOfWifi) { // 더 많은 공유기가 설치될 수 있는 경우
start = midGap + 1;
result = midGap;
}
// 공유기 설치 공간이 부족한 경우
else end = midGap-1;
}
System.out.println(result);
}
}
이러한 문제의 경우 데이터를 하나씩 확인하게 된다면 실행시간이 매우 많이 나올 것이다. 문제를 풀 때는 데이터의 개수를 보고 이번 문제와 같이 10억개와 같이 많은 데이터에 대해 돌려야한다면
2진 탐색과 같은 자료구조를 사용하여 와 같은 시간복잡도를 만들도록 출제자가 출제했다는 것을 알아차려야한다!!!
그리하여 이번 문제는 이진탐색을 이용하여 문제를 풀어봤다.
코드의 실행 구조
1. 처음에는 넓은 간격으로 탐색을 한다.
2-1. 탐색을 하였을 때 설치하려는 공유기의 개수보다 적은 개수가 설치됐을 경우 간격을 줄인다.
2-2. 공유기의 개수보다 많이 설치되었을 경우 간격을 넓힌다.