문제
https://school.programmers.co.kr/learn/courses/30/lessons/43238
입력
입국심사를 기다리는 사람 수 n
각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times
출력
모든 사람이 심사를 받는데 걸리는 시간의 최솟값
풀이
제한조건
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
접근방법
수의 범위가 매우 크다.
적절한 시간을 찾아야 하는데, 단순하게 탐색해서는 시간내에 찾을 수 없다.
이분 탐색을 통해 반으로 줄여가며 정답을 찾아야 한다.
(이분탐색 : https://velog.io/@hyeokkr/%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89)
특정 시간을 기준으로 완료된 사람 수를 파악하는 방법은
각 심사위원들의 심사시간으로 나눈 몫을 통해 알 수 있다.
심사를 통과한 사람 수
= 현재시간 / 1번 심사관의 심사시간
+ 현재시간 / 2번 심사관의 심사시간
+ ...
+ 현재시간 / N번 심사관의 심사시간 주의해야할 점은 Type 이다.
주어진 매겨변수가 모두 int type이기 때문에
Type Casting이 필요하다.
또한 int의 범위로 충족시킬 수 있는 값이 없다는 점도 반드시 주의해야 한다.
코드
import java.util.*;
class Solution {
public long solution(int n, int[] times) {
Arrays.sort(times);
int len = times.length;
long min = (long)n * times[0] / len;
long max = (long)n * times[len - 1];
while(min <= max){
long count = 0;
long mid = (min + max) / 2;
// mid 시간 기준으로 완료된 사람 수를 구한다.
for(int i : times){
count += mid / i;
}
// 완료된 사람이 부족한 경우 재 탐색
if(count < n){
min = mid + 1;
}else{
// 완료된 사람이 많은 경우, 시간이 너무 많이 주어진 경우
// 줄 일 수 있는 최대로 줄인다.
max = mid - 1;
}
}
return min;
}
}