💡 문제
권장 시간
- 1시간
소요 시간
- 1시간 10분 + a
풀이 코드
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; // 가장 긴 심사가 n번 반복되는 경우
while (left <= right) {
// mid 시간으로 현재의 left, right가 적절히 설정됐는지 (심사가 가능한지) 판단
long mid = (left + right) / 2;
// 각 심사대가 mid 시간 내에 완료할 수 있는 사람 수 계산
long complete = 0;
for (int i = 0; i < times.length; i++) {
complete += mid / times[i];
}
// mid 시간 내에 심사 완료 못한 경우
if (complete < n) {
// 최소 시간 늘리기
left = mid + 1;
}
// mid 시간 내에 심사 완료한 경우
else {
// 시간을 더 줄여도 되는지 확인하기 위해 right를 mid - 1로 이동시킴
right = mid - 1;
answer = mid;
}
}
// 최종 최소 시간 반환
return answer;
}
}
주요사항
이분탐색은 처음 풀어보는데 이해하는 데 꽤 오래 걸렸다.
일단 제한사항을 보고 터무니없이 높은 숫자에 반복문으로 풀면 안된다는 것은 알았다.
근데 이 문제를 대체 어떻게 이분탐색으로 풀지..? 싶었는데, 그 이유는 ‘기준’을 몰랐던 것..!
그리고 이분탐색인걸 알았어도 심사가 끝나는 시간에만 집착하다보니 ‘심사가 완료되는 사람 수’로 풀 생각을 전혀 못했다.
개념이 생소하고 처음 풀어보는 유형이라 손도 못댔는데, 다음에는 좀 더 활용할 수 있기를!