문제
https://programmers.co.kr/learn/courses/30/lessons/43238#
코딩테스트 연습 - 입국심사
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한
programmers.co.kr
풀이
이분탐색을 이용해서 풀어야 하는 문제이다.
결과 값이 크기 때문에 타입에 유의해야 한다.
아래와 같이 초기화 한다.
심사의 최대 시간 = 최소 심사시간 * n
심사의 최소 시간 = 최소 심사시간
그리고 이분탐색을 진행한다.
mid값을 총 걸리는 시간이라고 가정한다면,
mid값/심사시간 = 해당 심사관이 심사하는 사람의 수가 된다.
그리고 모든 심사관의 수를 합하면 mid시간 동안 심사한 사람의 총 인원이 구해진다.
이 인원이 n이 되는 최소 mid시간을 찾는 것이 목표이다.
소스코드
import java.util.*;
class Solution {
public long solution(int n, int[] times) {
Arrays.sort(times);
// 심사 최소 시간
long L = times[0];
// 심사 최대 시간
long R = times[0]*(long)n;
long minVal = 0;
while(L <= R){
long mid = (L+R)/2;
// 여기서 mid는 총 걸리는 시간
int checked = 0;
for(int time : times) {
// 총 시간/각 심사관의 심사시관 = 해당 시간 동안 심사하는 사람의 수
// 즉, 총 걸리는 시간 동안
// 각 심사관이 심사하는 사람의 수를 합했을 때
// 'n'이 되는 최소 시간을 찾는 것이 목표
checked += mid/time;
if(checked >= n){
minVal = mid;
R = mid - 1;
break;
}
}
if(checked < n){
L = mid + 1;
}
}
return minVal;
}
}
'💡Problem Solving > Programmers' 카테고리의 다른 글
[프로그래머스] 합승 택시 요금 (Java) (0) | 2021.10.31 |
---|---|
[프로그래머스] 멀리 뛰기 (Java) (0) | 2021.10.29 |
[프로그래머스] 2 x n 타일링 (Java) (1) | 2021.10.29 |
[프로그래머스] 야근 지수 (Java) (0) | 2021.10.29 |
[프로그래머스] 추석 트래픽 (Java) (0) | 2021.10.29 |