https://programmers.co.kr/learn/courses/30/lessons/43238
코딩테스트 연습 - 입국심사
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한
programmers.co.kr
저는 이분탐색을 통해 문제를 해결하였습니다.
이분 탐색을 통해 해당 시간이 해당 인원을 검사할 수 있는지 판단하였습니다.
해당 인원을 검사할 수 있는 시간이 된다면 end를 줄이고, 검사할 시간이 안된다면 start를 늘려가면서 검사에 필요한 최소 시간을 찾아나갔습니다.
class Solution {
public long solution(int n, int[] times) {
long answer = binearySearch(n,times);
return answer;
}
private static final long START_TIME = 1L;
private static final long END_TIME = 1_000_000_000L * 1_000_000_000L;
private long binearySearch(int n,int[] times){
long start = START_TIME;
long end = END_TIME;
long result = 0;
while(start <= end){
long mid = (start + end) / 2;
if(checkInTime(n,times,mid)){
result = mid;
end = mid -1;
}else{
start = mid +1;
}
}
return result;
}
private boolean checkInTime(int n , int[] times, long totalTime){
long cnt = 0;
for(int time : times){
cnt += totalTime / time;
}
if(cnt >= n){
return true;
}else{
return false;
}
}
}
'알고리즘' 카테고리의 다른 글
프로그래머스 [3차] 압축 (JAVA) (0) | 2022.06.23 |
---|---|
프로그래머스 섬 연결하기 (JAVA) (0) | 2022.06.22 |
프로그래머스 하노이의 탑(JAVA) (0) | 2022.06.20 |
프로그래머스 숫자의 표현 (JAVA) (0) | 2022.06.19 |
프로그래머스 올바른 괄호 (JAVA) (0) | 2022.06.18 |