입국심사(프로그래머스, Lv 3, Java)

1. 입국심사

문제링크: https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사 | 프로그래머스

알고리즘 설명:

처리시간이 다른 심사원들의 최소 걸리는 시간을 구하는 문제. - 이분탐색

• 최소로 걸릴 수 있는 시간 0초 - start, 최대로 걸릴 수 있는 시간 가장 오래걸리는 심사원 시간 * 인원수(n) - end
• 가장 오래걸리는 심사원은 오름차순 정렬을 한 뒤 마지막 값을 가져오는 것으로 찾았다.
• 이분 탐색을 하면서 나온 sum 값이 mid 값보다 작거나 같을 때 답이 될 가능성이 있다.
• 답이 될 가능성이 있는 값들 중 가장 낮은 값이 정답

막혔던 지점:

• 초기 end 값 즉 가장 오래 걸릴 수 있는 시간 값을 구할 때 곱하기 n을 해주었는데 long 타입으로 형변환을 해주지 않았다. - 그 결과 5개만 맞고 다 틀림...
• 형변환 후 전부 정답

코드(Java)

package test2;

import java.util.Arrays;

public class ImigrationEx {

	public static long solution(int n, int[] times) {
		Arrays.sort(times);
		long start = 0;
		long end = (long)times[times.length - 1] * n;
		long mid = 0;
		long answer = Long.MAX_VALUE;
		while (start <= end) {
			long sum = 0;
			mid = (start + end) / 2;
			for (int time : times) {
				sum += mid / time;
			}
			if (sum < n) 
				start = mid +1;
			 else {
				if(answer>mid)
					answer = mid;
				end = mid - 1;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		solution(20,new int[] {2,3,4,5,2,7,1,2});

	}

}