문제를 직관적으로 접근하면 모든 경우의 수를 탐색하는 브루트포스(완전 탐색) 방식이 떠오르지만, 이 방식은 입력 크기가 커질 경우 시간 초과 또는 메모리 초과가 발생한다. 문제를 효율적으로 해결하기 위해 “최솟값을 지정하고, 그 값을 기준으로 바위를 제거했을 때 N개의 바위를 제거할 수 있는지 확인하는 방법“이 핵심이다. 이 방법은 직관적으로 떠오르는 완전 탐색(브루트포스) 방식을 개선하여, 시간 복잡도를 크게 줄이는 접근이다.
- 최솟값 min_distance를 기준으로 이진 탐색 수행:
- min_distance는 거리 간의 최솟값을 의미하며, 이 값을 점진적으로 증가시키면서 조건을 만족하는지를 확인
- min_distance의 탐색 범위는 [1,distance]
- 특정 min_distance에서, 조건(거리 간 최솟값이 min_distance 이상인 상태로 N개의 바위를 제거 가능)을 만족하면 더 큰 값으로 범위를 조정
- 조건 확인 방법:
- 주어진 min_distance에 대해, 출발지점부터 도착지점까지 rocks 배열을 순회하면서 거리 차이를 계산
- 거리 차이가 min_distance보다 작으면 해당 바위를 제거
- 제거된 바위의 개수가 N을 초과하면, 해당 min_distance는 조건을 만족하지 못하므로 탐색 범위를 줄임
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class SteppingStone {
public int solution(int distance, int[] rocks, int n) {
int answer = 0;
int low = 0;
int high = distance;
List<Integer> rockList = Arrays.stream(rocks).boxed().sorted().collect(Collectors.toList());
rockList.add(distance);
while (low <= high) {
int current = 0;
int removeCount = 0;
int mid = (high + low) / 2;
int minDistance = Integer.MAX_VALUE;
for (int rock : rockList) {
int diff = rock - current;
if (diff < mid) {
removeCount++;
} else {
current = rock;
minDistance = Math.min(minDistance, mid);
}
}
if (removeCount > n) {
high = mid - 1;
} else {
answer = minDistance;
low = mid + 1;
}
}
return answer;
}
}