🙋🏻♀️이진탐색 사용!
엄청엄청 많이 헷갈렸고, 고민했던 문제다.
Troubleshooting
public class Main {
public static int[] now;
public static ArrayList restArea;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
now = new int[N+2];
restArea = new ArrayList<Integer>();
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
now[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(now);
now[0] = 0;
now[N+1] = L;
for(int i=0; i<N+2; i++) {
System.out.println(now[i]);
}
for(int i=1; i<N+2; i++) {
int rest = now[i] - now[i-1] -1;
restArea.add(rest);
}
for(int j=0; j<M; j++) {
int max = (int)Collections.max(restArea);
int start = 1;
int end = max;
Collections.sort(restArea);
int middle = (start + end) /2;
restArea.remove(Integer.valueOf(max));
restArea.add(end-middle);
restArea.add(middle-start);
}
System.out.println((int)Collections.max(restArea));
}
}문제
정상이라면 '0 200 701 800 1000'이 들어가야하는데, index 1에 값이 제대로 안들어가고 하나씩 밀려들어갔다. 그래서 마지막값도 1000으로 덮어써졌다.
원인
양 끝값 제외한 값들을 먼저 넣고, 정렬을 수행한게 문제였다.
양 끝은 여전히 0인데, 정렬하니 맨 뒷값이 앞으로 오게되기때문에 오류가 발생했다.
해결
now[0] = 0;
now[N+1] = L;
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
now[i] = Integer.parseInt(st.nextToken());
}now배열의 처음과 끝에 값을 먼저 넣고, 나머지 값들을 채우는 걸 이후에 진행하니 해결됐다.
Troubleshooting 2
계속 다른 답이 나오고, 손으로 증명해봐도 답이 다르게나와서 코드 문제가 아님을 알았다.
매번 주유소 사이 거리의 최댓값을 구해서 절반으로 나누고 이 과정을 반복하면 최댓값의 최솟값이 보장되지 않는다.
기존 구간을 3개로 나누는데, 이 방법을 진행한다면
이런식으로 나누어지기 때문이다.
이는 기존 구간이 짝수개로 나누어질때에도 마찬가지다.
2의 배수개로 나누어지면 정답로직으로 나눌때와 최댓값의 최솟값이 동일하지만, 그게 아닌 짝수개로 나누어지는 경우에는 위 사진의 케이스와 동일하기 떄문이다.
따라서 주유소 사이 가능한 거리를 기준으로 개수를 카운트하며 이분탐색을 진행해야한다!
Troubleshooting 3
public class Main {
public static int[] now;
static int N;
static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
now = new int[N+2];
now[0] = 0;
now[N+1] = L;
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
now[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(now);
binarySearch(1,L-1);
}
public static void binarySearch(int start, int end) {
while(start <= end) {
int count = 0;
int middle = (start + end) /2;
for(int i=N+1; i>0; i--) {
int dis = now[i] - now[i-1] -1;
count += dis/middle;
}
if(count>M) start = middle +1;
if(count<M) end = middle -1;
}
System.out.println(start);
}
}문제
예제를 입력하면 콘솔에 결과가 안찍힌다.
원인
디버깅해보니
71거리로 주유소를 세운다고 가정했을 때, 7개가 들어가는데 이렇게 'count == M' 일때는 start, end를 변경해주는 코드가 없어서 while문을 빠져나오지 못한다.
해결
최댓값의 최솟값을 구하는것이기때문에, count == M인 middle이 정답이 될 경우에도 middle이 더 작을 수 있는지 체크해야한다.
따라서 count == M인 경우에는 end = middle -1 을 헤야한다.
제출코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static int[] now;
static int N;
static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
now = new int[N+2];
now[0] = 0;
now[N+1] = L;
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
now[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(now);
binarySearch(1,L-1);
}
public static void binarySearch(int start, int end) {
while(start <= end) {
int count = 0;
int middle = (start + end) /2;
for(int i=N+1; i>0; i--) {
int dis = now[i] - now[i-1] -1;
count += dis/middle;
}
if(count>M) start = middle +1;
if(count<=M) end = middle -1;
}
System.out.println(start);
}
}다른풀이
이 풀이는 어디에서 본 풀이가 아니라, 토론후에 얻은 풀이다.
기존 휴게소 사이의 거리를 저장한 배열을 A라고 하자.
휴게소 사이의 거리를 없데이트 할 배열을 B라고 하자.
A 배열은 수정하지않고, B 배열만 수정한다.
처음에는, A와 동일한 내용을 B에 넣는다.
B의 최댓값을 구하고, 이것에 해당하는 A배열데이터를 /n 해준다.
n은 해당 데이터를 처음 나누면 2, 또 나누면 3, 또 나누면 4 .. 이렇게 증가하기때문에 각 데이터마다 몇 번 나누었는지 체크하는 배열을 하나 더 만들어야한다.
나눠지는 거리의 크기가 달라도, 나눠지는 거리의 최대값만 저장해주면 된다.
이렇게 총 M번 반복한 후 B배열의 최댓값을 출력하면 정답이다.
시간복잡도는 O(M) = O(100), 공간복잡도는 N크기의 배열 3개를 사용하는데 N의 최대가 50이므로 150이고, int타입이므로 150*4byte = 600byte 이다.
따라서 이 로직을 사용해도 계산이 가능할 것 같다.
하지만, 이진탐색이 훨씬 빠르다!
참고
https://moonsbeen.tistory.com/273
https://gusdnr69.tistory.com/277
