문제의 distance 는 최대 1,000,000,000 으로 매우 커서, 임의로 n 개의 바위를 선택해서 제거하는 방법으로는 문제를 풀 수 없을 것이라고 생각함
따라서 바위 위치를 거리로 정렬을 한 뒤, 바위 사이 거리를 모은 배열을 구하고 그 사이 거리가 가장 짧은 것 부터 순서대로 바위를 제거하기로 결정함
좌측과 우측의 바위중에 더 짧은 거리에 있는 바위와 합치기로 결정
public int solution(int distance, int[] rocks, int n) {
Arrays.sort(rocks);
List<Integer> dis = new ArrayList<>();
dis.add(rocks[0] );
for (int i=1; i<rocks.length; i++) {
dis.add(rocks[i] - rocks[i - 1]);
}
dis.add(distance - rocks[rocks.length - 1]);
int index = 0;
int min = Integer.MAX_VALUE;
for (int i=0; i<n; i++) {
for (int j=0; j<dis.size(); j++) {
if (min > dis.get(j)) {
min = dis.get(j);
index = j;
}
}
// 최소 거리 구함
if (index == 0) {
int t = dis.get(1);
dis.remove(1);
dis.set(0, dis.get(0) + t);
}
else if (index == dis.size() - 1) {
int t = dis.get(dis.size() - 1);
dis.remove(dis.size() - 1);
dis.set(dis.size() - 1, dis.get(dis.size()) + t);
}
else {
int l = dis.get(index - 1);
int r = dis.get(index + 1);
if (l > r) {
// 우측 것과 더함
dis.remove(index + 1);
dis.set(index, dis.get(index) + r);
} else {
int t = dis.get(index);
dis.remove(index);
dis.set(index - 1, t + l);
}
}
min = Integer.MAX_VALUE;
}
return dis.stream().sorted().collect(Collectors.toList()).get(0);
}
1,2,3,8 번의 테스트 케이스 실패
다음과 같은 케이스에서 실패함
distance => 16
rocks => [4, 8, 11]
n => 2
답: 8
내 풀이 : 5
위 문제에서 거리가 4인 바위와 11인 바위를 제거해야 가장 큰 거리 8이란 수를 얻을 수 있는데,
가장 짧은 거리인 8바위와 11바위 사이 거리 3을 키우기 위해서 8바위를 제거해버린 것이 문제
즉, 지금 당장의 짧은 거리만 찾아서 문제를 해결하려다 보니 이런 오답 발생
두번째 시도 (정답)
기준 거리 T를 잡고 이 거리보다 사이거리가 가까운 돌이 있다면 제거하는 방법으로 문제 풀이 변경
1부터 1,000,000,000 까지 차근 차근 탐색을 진행하면 time over 될 것이라고 예상을 해서 이분 탐색으로 진행하기로 함
제거한 돌을 모두 모았을 때 n 보다 많다면 더 짧은 거리 T를 기준으로 탐색해봐야 하고, n보다 적다면 사이 간격을 더 크게 잡아 탐색함
이 때 거리를 구하는 기준을 이분 탐색으로 정함
탐색해야할 기준 거리를 T 라고 하고 제거한 돌의 개수를 R, 거리를 D라고 할 때 다음과 같이 탐색할 수 있다.
T R D n
50 10 100 4
24 3 100 4
37 4 100 4
처음은 0 ~ 100 사이 50 탐색 => 10개 돌 제거됨
너무 많은 돌을 제거 했다. 더 짧은 거리 0 ~ 49(50은 이미 탐색함) 사이에서 24 탐색 => 3개 돌 제거됨
제거한 돌이 너무 적다. 제거할 수 있는 돌이 더 있다. 25 (24는 이미 탐색) ~ 49 사이에서 37 탐색 => 4개 돌 제거됨 (기준 만족)
public int solution(int distance, int[] rocks, int n) {
int result = 0;
Arrays.sort(rocks);
int[] rockList = new int[rocks.length + 2];
rockList[0] = 0;
for (int i = 0; i<rocks.length; i++) {
rockList[i + 1] = rocks[i];
}
rockList[rockList.length - 1] = distance;
int l = 0;
int r = distance;
while (l <= r) {
int T = (l + r) / 2;
int R = 0;
// 이전 돌의 인덱스
int i = 0;
// 돌 제거하기 시작
for (int j=1; j<rockList.length; j++) {
// 2, 11, 14, 17, 21
// 거리가 짧으면 돌 제거, 인덱스는 그대로
if (rockList[j] - rockList[i] < T) {
R++;
} else {
i = j;
}
// 마지막 돌부터 distance 까지 거리가 T 보다 짧으면 마지막 돌을 제거하는 것으로 결정
}
// 제거한 돌이 더 많으면 짧은 거리에서 찾아보기
if (R > n) {
r = T - 1;
} else {
// 제거한 돌이 더 적거나 같으면
result = T;
l = T + 1;
}
}
return result;
}
