문제
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
해결방안
이 문제는 이분탐색으로 풀수 있는 문제이다.
이분탐색을 간단하게 설명하면 left와 right를 정하고 그 중간값 mid값을 정한다. 그 뒤 찾고 싶은 값이 mid보다 크면 left를 mid로 바꾸고 다시 left와 right를 기준으로 찾는다. 반대로 mid보다 작으면 right값을 mid값으로 바꾸고 찾으면 된다.
이 문제에서는 찾아야 하는 즉 target이 사람 수 여야한다. 사람 수 를 구하기 위해서는 주어진 시간 / 해결시간 이 되어야 한다. -> 사람 수 = 주어진 시간 / 해결 시간
그리고 mid를 주어진 시간으로 구하면 된다. 해결시간은 주어진 times의 원소들
따라서 사람 수 = mid / times[i] 이다.
사람 수가 n보다 크거나 같다면 주어진 시간안에 해결 가능하거나 더 처리할 수 있으므로 최소 시간이 아닐수 있다. 따라서 right에 mid-1를 넣어서 다시 해결해야 한다.
반대로 사람 수가 n보다 작다면 주어진 시간안에 해결이 불가능 하다는 의미이다. 따라서 left에 mid+1의 값을 넣어주고 다시 해결해야한다.
** 주의 이분탐색에서 한번 탐색을 했지만 원하는 값을 찾지 못했다면 mid는 자기가 원하는 값이 아닌것이다. 따라서 right나 left에 mid에 +-1을 해줘야 한다.
1. times배열을 오름차순으로 정렬시킨다.
2. start에는 최선의 경우인 속도가 1이며 사람이 1명일때인 1을 대입하고 end에는 최악의 경우인 times배열의 마지막 원소를 대입한다.
3. start가 end와 같이질 때까지 반복하며 times의 원소를 하나하나 mid의 값을 나누고 sum에 더해준다.
-> sum의 값은 주어진 시간이 mid일때 심사관들이 심사해준 사람들의 합
4. sum이 n 보다 크거나 같으면 시간을 줄일 수 있으므로 end에 mid-1값을 넣어준다. 그리고 answer에 mid값을 넣어준다.
5. 반대로 sum이 n보다 작으면 심사된 사람의 수가 목표치보다 작은 것이므로 start에 mid+1의 값을 넣어준다.
6. while문이 끝나면 answer를 리턴해주면 된다.
코드
package programmers_3;
import java.util.Arrays;
public class immigration {
public static void main(String[] args) {
int n = 6;
int[] times = {7,10};
immigration s = new immigration();
System.out.println(s.solution(n,times));
}
public long solution(int n,int[] times){
long answer = 0;
Arrays.sort(times);
long start = 1;// 최선의 경우
long end = (long)times[times.length-1] * n;//최악의 경우
while(start <= end){
long sum = 0;
long mid = (start+end)/2;
for(int time : times){
sum += mid/time;// 심사관마다 중간시간을 기준으로 심사할 수 있는 사람의 수의 합
}
if(sum >= n){ // 심사하는 사람의 수가 더 많거나 같으므로 시간을 줄일 수 있다.
end = mid-1;
answer = mid;
}else{// 심사하는 사람의 수가 적으므로 시간을 늘려야한다.
start = mid+1;
}
}
return answer;
}
}
댓글