[Programmers] 입국심사 - JAVA
📚 Problem
- 처음에 모든 심사대는 비어있습니다
- 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다
- 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다
- 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다
- 모든 사람이 심사를 받는데 걸리는
최소 시간
찾기
📝 Solution
Key Idea
- 각 심사관이 걸리는 시간의 배열을
오름차순 정렬
합니다left
에 0 과right
에 가장 시간이 오래 걸리는 최악의 경우인times[times.length - 1] * n
을 넣습니다- 두 시간의 중간 지점인
mid
로 각 심시관들이mid
시간동안 심사할 수 있는 사람의 수를sum
에 모두 더해줍니다- 만약
sum
이 심사를 받아야할 사람수n
보다 작을 경우 시간을 더 늘려야 하기 때문에left
에mid + 1
을 넣고 오른쪽으로 다시 이분탐색 합니다- 그렇지 않다면, 해당 시간에 모든 사람을 심사할 수 있으므로
answer
에mid
시간을 넣어주고,right
에mid - 1
을 넣고 왼쪽으로 다시 이분 탐색하여 최소의 시간을 찾습니다
while (left <= right) {
mid = (left + right) / 2;
long sum = 0;
for (int time : times)
sum += mid / time;
if (sum < n)
left = mid + 1;
else {
right = mid - 1;
answer = mid;
}
}
💻 Code
Solution.java
import java.util.Arrays;
class Solution {
public long solution(int n, int[] times) {
long answer = Long.MAX_VALUE;
Arrays.sort(times);
long left = 0, mid, right = (long) times[times.length - 1] * n;
while (left <= right) {
mid = (left + right) / 2;
long sum = 0;
for (int time : times)
sum += mid / time;
if (sum < n)
left = mid + 1;
else {
right = mid - 1;
answer = mid;
}
}
return answer;
}
}
SolutionTest.java
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
public class SolutionTest {
Solution solution;
@BeforeEach
public void setSol(){
solution = new Solution();
}
@Test
public void solution_1(){
long result = solution.solution(6, new int[]{7, 10});
assertEquals(28, result);
}
@Test
public void solution_2(){
long result = solution.solution(10, new int[]{6, 8, 10});
assertEquals(30, result);
}
}
Author And Source
이 문제에 관하여([Programmers] 입국심사 - JAVA), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@choi-jaewon/Programmers-입국심사-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)