알고리즘
[Java] 프로그래머스 - 입국심사
J3SUNG
2023. 8. 28. 14:55
728x90
이분탐색 문제입니다.
n명의 친구들이 전부 심사대를 통과하는데 걸리는 시간을 구해야합니다.
심사대는 전부 시간이 다릅니다.
1. 시간을 구합니다.
2. 해당 시간으로 통과할 수 있는 사람들 수를 구합니다.
3-1. 사람들 수가 n보다 많거나 같다면 더 작은 경우가 있는지 확인합니다. => 1
3-2. 사람들 수가 n보다 적다면 불가능 한 경우로 가능한 경우가 있는지 확인합니다. => 1
위의 과정을 반복해서 최적의 결과값을 찾아냅니다.
해당 과정에서 시간을 구하는 과정은 이분탐색을 사용했습니다.
class Solution {
public long solution(int n, int[] times) {
long answer = 1_000_000_000L * 1_000_000_000L;
long start = 1;
long end = 1_000_000_000L * 1_000_000_000L;
while (start <= end) {
long mid = (start + end) / 2;
long temp = n;
for (int i = 0; i < times.length; i++) {
temp -= mid / times[i];
if (temp <= 0) {
break;
}
}
if (temp <= 0) {
end = mid - 1;
answer = Math.min(answer, mid);
} else {
start = mid + 1;
}
}
return answer;
}
}