programmers.co.kr/learn/courses/30/lessons/43238
코딩테스트 연습 - 입국심사
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 �
programmers.co.kr
최적의 값을 찾아야하기때문에 두 부분으로 분할하여 탐색을 하도록 합니다.
범위를 줄여나가며 탐색을 할 것이기 때문에 이분탐색을 이용합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import java.util.Arrays;
class Solution {
public long solution(int n, int[] times) {
Arrays.sort(times);
long minTime = 1;
long maxTime = (long) times[times.length-1] * n;
return binarySearch(minTime, maxTime, times, n, 0);
}
private long binarySearch(long start, long end, int[] times, int people, long answer) {
if (start > end) {
return answer;
}
long mid = ( start + end ) / 2;
long limit = 0;
// 처리 가능한 시간을 구합니다.
for (int time : times) {
limit += mid / time;
}
// 처리 시간 보다 더 클 경우
if (limit < people) {
return binarySearch(mid + 1, end, times, people, answer);
}
return binarySearch(start, mid - 1, times, people, mid);
}
}
|
cs |
