99클럽 코테 스터디 3일차 TIL : 이분탐색(프로그래머스 level3. 입국심사)

 

Programmers leve3. 입국심사

 

 

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

 

---

 

 

⭐나의 풀이

 

🔎문제 정리)

입국심사 기다리는 사람수 : n
심사관이 한 명 심사하는데 걸리는 시간이 담긴 배열 : times
심사관 수 : people

심사받는데 걸리는 시간의 최소값 return 하기

제한) 1<=n<=10^9 (최대10억명)
1<=time<=10^9
1<=people<=100000 = 10^5

예) n=6, times=[7,10]
return 28


💡 아이디어) 
1. 입국심사 자보다 심사관 수가 많으면, 가장 오래걸리는 심사관의 시간이 최소값임
=> n이 people보다 작으면 times중의 최대값이 반환
=> if(n<people) return times의 최대값 (* times배열을 오름차순으로 정렬해서 마지막 값)

2. 
1  2    3  4   5   6  /   
7 10 14 20 21 28/ 30  .... (7의 배수와, 10의 배수의 배열)
=> 값이 28일 때, 멈추게 됨

3. 이분탐색을 어떻게 이용하지?

=> left , right 값을 시간으로 두고, n명을 처리한 시간 중 가장 최솟값을 찾자.

left = 1
right = 10^16(시간)
answer = right


for(left<=right){
    mid = (left+right)/2;      
    cnt = 0;   						//mid시간 내 처리할 수 있는 명수 총합
   
    for(int i=0;i<times.length;i++){ //감독관 1명씩 순서대로
        cnt += mid/times[i];   		 // 처리할 수 있는 명수를 더해주기
    }

    if(n<=cnt){ 					//mid 시간 내에 n명을 처리할 수 있으면
        answer = mid;				//정답을 mid 시간으로 변경
        right = mid-1;				//right 값을 mid-1로 설정
    } else{
        left = mid+1;
    }

}

 

 

✔ 최종 제출한 코드)

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long left = 1L;
        Arrays.sort(times);	//오름차순 정렬
		long right = (long)n*times[0];
		long answer = right; //최소값

		while(left<=right){
			long mid = (left+right)/2;
			long cnt = 0;   //mid시간내 처리할 수 있는 명수 총합
				   
			for(int i=0;i<times.length;i++){
				cnt += mid/times[i];
			}
					
			if(n<=cnt){
				answer = mid;
				right = mid-1;
			} else{
				left = mid+1;
			}
		}
		return answer;
    }
}

 

 ⭐오늘의 회고

✔ 최대 값 설정

문제) n값의 제한이 1<=n<=10^16 이어서 단순히 right값을 10^16으로 설정

개선) right 값을 n*times최솟값으로 설정

시간이 아무리 많이 걸려도 가장 빠르게 일하는 심사관 한명이 다 처리한 시간을 넘을 수 없다.

 

=> 항상 최대 값 설정하는 것을 더 효율적으로 할 수 없을까에 대해 더 고민해보자.