[프로그래머스] 입국심사 -Java

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

import java.util.Arrays;
class Solution {
		long answer;

		public long solution(int n, int[] times) {
			answer = Long.MAX_VALUE;
			long nn=n;
			Arrays.sort(times); // 시간순으로

			long left = 1;
			long right = times[times.length - 1] * nn;
			long mid = 0;
			long people = 0;

			while (left <= right) {
				people = 0;
				mid = (left + right) / 2;

				for (int i = 0; i < times.length; i++) {
					people += mid / times[i];
					if (people > nn) {// 너무 큼 숫자를 줄여야 함
						break;
					}
				}

				if (people < nn) { // 시간 부족 시간 늘려야 함
					left = mid + 1;
				} else { // 시간 충분
					right = mid - 1;
					answer = Math.min(answer, mid);
				}
			}
			return answer;
		}
	}

소요시간 : 1시간 20분

 

제한사항을 보면 무조건 이분탐색이다 라는 생각이 드는 문제입니다.

그렇긴 한데 어떤식으로 이분탐색을 해야 할 지 생각하는데 정말 시간이 많이 들었습니다.

 

우선 결론을 말씀드리자면 시간을 기준으로 이분탐색을 합니다.

 

입국심사를 기다리는 총 사람의 수는 6명, 심사관은 2명 ( 걸리는시간 : 7초 , 10초) 입니다.

 

우선 sort를 통해 심사관들의 심사하는 시간을 오름차순으로 정렬해줍니다.

그리고 left=1, right=최대 오래 걸리는시간 ( 배열의 마지막 값 * 사람의 수 ) 를 해줍니다.

문제에서는 left =1 , right = 10*6 = 60 입니다.

 

이상태로 이분탐색을 시작합니다.

 

mid=(left+right)/2   -> 30

시간 : 30

1번 심사관 : 4명

2번 심사관 : 3명    

-> 총 7명으로 입국심사를 기다리는 인원보다 많은 사람을 해결할 수 있습니다.  시간을 줄여야 하기 때문에 right=mid-1을 합니다

 

mid=(left+right)/2 -> 15

시간 : 15

1번 심사관 : 2명

2번 심사관 : 1명 

-> 총 3명으로 턱없이 부족한 시간이란걸 알 수 있습니다. 시간을 늘려야 하기 때문에 left=mid+1을 합니다.

 

이런식으로 이분탐색을 계속 하다보면 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구할 수 있습니다!