문제
https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=java
풀이방법
우리가 찾아야 할 값은 모든 사람이 심사를 받는데 걸리는 시간의 최솟값이다.
그렇다면 시간의 범위는 0 ~ 가장 오래 걸린 심사시간 일 것이다.
left : times[0] , right : 모든 사람이 가장 오래걸리는 심사대에서 심사를 받은 시간
-
먼저 각 심사관 별 심사시간이 담긴 times 배열을 오름차순으로 정렬한다.
-
left = times[0], right = times[times.length-1] * n(사람 수)로 설정한다.
- left는 1초부터 해도 되지만 탐색의 시간을 줄이기 위해 답이 될 수 있는 수 중 가장 적은 시간인 times[0]으로 뒀다.
- right는 최악의 경우로 설정. 최대시간 = 가장 오래 걸리는 시간 * 인원수
-
이분탐색을 진행한다. 반복문의 제한은 left <= right
3-1. mid 시간을 구한다. (left + right) / 2
3-2. 각 심사대 별로 주어진 시간 mid동안 몇명의 사람을 심사할 수 있는지 합산한다.
(ex. mid = 10, times = {2, 3, 4}인 경우, 10 / 2 + 10 / 3 + 10 / 4로 총 5+3+2=10명 가능3-3. 심사한 총 사람 수(complete)가 n보다 작을경우,
해당 시간동안 모든 사람을 검사할 수 없다는 뜻이다. left를 mid + 1로 로 이전한다.3-4. n보다 크거나 같을 경우
answer = mid를 넣어둔다. 다만 해당 경우보다 더 최솟값이 나올 수 있다.
right = mid - 1로 설정하여 범위를 줄여준다. -
반복문이 끝나고 answer를 return한다.
왜 complete == n을 따로 빼지 않았을까?
우리가 찾아야 할 값은 "모든 사람을 심사하는 시간의 최솟값"이다. 즉, n과 complete가 딱 맞아떨어지게 같은 경우가 없을 수도 있다. 즉 '여분의 시간'이 남은 채로 모두 심사하는게 최선의 선택일 수도 있다.
따라서 complete >= n일 경우에 answer에 값을 저장해준 후, right의 범위를 줄여보며 더 빠른 시간이 있으면 answer를 바꿔주고, 없다면 반복문을 빠져나와(left > right인 경우) 로직이 끝나게 된다.
코드
import java.io.*;
import java.util.*;
class Solution {
public long solution(int n, int[] times) {
long answer = 0;
Arrays.sort(times);
long left = times[0];
long right = times[times.length-1] * (long) n;
long mid = 0;
System.out.println(right);
while(left <= right) {
mid = (left + right) / 2;
long sum = 0;
for(int time : times) {
sum += mid/time;
}
if(sum < n) {
left = mid + 1;
} else {
answer = mid;
right = mid - 1;
}
}
return answer;
}
}