이분탐색인 힌트를 못보고 했으면 조합 다 뽑아서 일일이 계산했을 것 같다...
그 마저도 n의범위가 1 <= n <= 50000 이어서 결국 틀렷을 것 같다.
해당 문제는 이분탐색 문제인데, 정답으로 원하는 것은 특정 돌을 삭제했을 때 돌과 돌 사이의 거리 값들의 최솟값 중 최대값이다.
말이 좀 어려운데 예를 들어서,
distance = 25 (도착 지점까지의 거리로 마지막 돌과 도착지점 사이의 거리도 고려해야 한다. 비슷하게 0부터 첫 번째 위치의 돌까지의 거리도 고려해야 한다.)
rocks = [2, 14, 11, 21, 17] (정렬되지 않은 상태로 들어오므로, 정렬해줘야 한다)
n = 2 (지울 돌의 갯수이다)
위와 같은 경우 [21, 17]을 제거할 경우 각각의 거리는 [2, 9, 3, 11]이 되고, 최솟값은 2이다.
이렇게 10개의 경우에 대해서 각각의 경우에 대해 모두 최솟값을 구한다.
그리고 10개의 최솟값 중 최댓값을 반환해주면 된다. (예시의 경우엔 4이다.)
따라서 이분탐색의 주체로 현재 최솟값들 중 최댓값으로 설정해야 한다.
left = 1, right = distance로 설정한 뒤 mid = (left + right) / 2로 설정한다.
풀이 방식은 다음과 같다.
- 돌과 돌 사이의 거리가 mid 값보다 작으면 해당 돌은 지워야하는 것으로 판단하고, remove_cnt를 1증가시킨다.
- 만약 remove_cnt가 n값보다 크면, 이는 현재 최솟값들 중 최댓값이 너무 크다는 것이기 때문에 right를 mid - 1로 설정해주면 된다.
- 반대로 n값보다 작거나 같은 경우엔 left를 mid + 1로 설정해주고, answer 값을 mid로 업데이트 해준다.
3-1. 여기서 remove_cnt 가 n이랑 같은 경우에만 answer를 업데이트해야하지않나 라고 생각할 수 있는데, 수학적으로 k개를 삭제했을 때 얻는 최솟값들 중 최댓값이 항상 k+1개를 삭제했을 때 얻는 최솟값들 중 최댓값보다 작기 때문에 remove_cnt가 n미만일 때 업데이트 해줘도 상관없다.
예를 들어,
distance = 23, rocks = [3, 6, 9, 10, 14, 17], n = 2일때, 모든 경우를 구하면
0 3 6 9 10 23 -> 3 3 3 1 3 -> 1
0 3 6 9 14 23 -> 3 3 3 5 9 -> 3
0 3 6 9 17 23 -> 3 3 3 8 6 -> 3
0 3 6 10 14 23 -> 3 3 4 4 9 -> 3
0 3 6 10 17 23 -> 3 3 4 7 6 -> 3
0 3 6 14 17 23 -> 3 3 8 3 6 -> 3
0 3 9 10 14 23 -> 3 6 1 4 9 -> 1
0 3 9 10 17 23 -> 3 6 1 7 6 -> 1
0 3 9 14 17 23 -> 3 6 5 3 6 -> 3
0 3 10 14 17 23 -> 3 7 4 3 6 -> 3
0 6 9 10 14 23 -> 6 3 1 4 9 -> 1
0 6 9 10 17 23 -> 6 3 1 7 6 -> 1
0 6 9 14 17 23 -> 6 3 5 3 6 -> 3
0 6 10 14 17 23 -> 6 4 4 3 6 -> 3
0 9 10 14 17 23 -> 9 1 4 3 6 -> 1
따라서 답은 3이 된다.
위 예제를 이분탐색을 하면 remove_cnt가 2가 되는 경우가 존재하지 않는다.
mid값이 3일 때, remove_cnt가 1일 때가 유일한 케이스로 answer가 업데이트되는데 이는 10을 삭제하는 케이스이다. (혹은 9)
만약 mid값이 3일 때 10을 포함하고 나머지 돌 중 1개를 추가적으로 삭제해도 돌들 사이의 거리가 3이상인 것이 보장되기 때문에 remove_cnt가 1일 때도 answer를 업데이트해줘도 된다.
코드는 아래와 같다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int distance, vector<int> rocks, int n) {
int answer = distance;
if(rocks.size() == n)
return distance;
sort(rocks.begin(), rocks.end());
rocks.push_back(distance);
int left = 1;
int right = distance;
while(left <= right) {
int mid = (left + right) / 2;
int current = 0;
int remove_cnt = 0;
for(int i=0;i<rocks.size();i++) {
int diff = rocks[i] - current;
if(diff < mid)
remove_cnt++;
else
current = rocks[i];
}
if(remove_cnt <= n) {
// remove_cnt < n 일때도 answer 업데이트해줘야함.
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
