문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43238
이분 탐색을 알고리즘은 알았지만 이 문제에 어떻게 적용시켜야할 지를 몰랐다.
다른 분들의 답을 참고하여 어떤 식으로 접근해야하는지를 학습했다.
보통 이분 탐색은 해당 타겟을 찾으면 종료한다.
이 문제는 최소값을 찾는 것이기 때문에 start
와 end
가 교차할 때까지 진행해야한다.
times
의 최대값 * n
)import java.util.Arrays;
class Solution {
public long solution(int n, int[] times) {
long minTime = Long.MAX_VALUE;
long start, end, mid;
long people;
Arrays.sort(times);
start = 0;
end = (long)times[times.length - 1] * (long)n;
while (start <= end) {
mid = (start + end) / 2;
people = 0;
for (int time : times) {
people += mid / time;
}
if (people >= n) {
minTime = Math.min(minTime, mid);
end = mid - 1;
} else {
start = mid + 1;
}
}
return minTime;
}
}