이분탐색 입국심사 JAVA 프로그래머스 코딩테스트

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

프로그래머스

 

import java.util.*;

class Solution {

	public long solution(int n , int[] times){
    
    	long answer = 0;
        
        Arrays.sort(times); //오름차순 정렬
        
        long min = 1;
        long max = (long)times[times.length-1]*2; //배열의 마지막(가장 긴 시간)*대기인원
        long mid = 0;
        long sum = 0;
        
        while(min<=max){
        
        	mid = (min + max)/2;
            sum = 0;
            
            for(int time : times){
            	sum += mid/time;
            }
            
            //중간 시간으로 했을 때 대기 인원을 다 못하면 중간 이후 시간부터 다시 비교
            //mid+1 ~ max 사이의 값의 중간값부터 시작
            if(sum < n) {
            	min = mid + 1;
            }else{
            	//중간 시간에서 대기 인원을 수용했다면 중간 이전 값들 중 최솟값을 찾아봄
                //1 ~ mid-1 의 범위에서 중간값부터 시작
            	max = mid - 1;
                answer = mid;
            }
            
        }
        
        return answer;
    
    }


}

 

n times return
6 [7, 10] 28

 

일 경우 

 

min		mid		max
1		30		60

 

sum = 30/7 + 30/10 = 4+3 = 7

 

n보다 크기 때문에 

 

answer = 7

max = 29

 

min		mid		max
1		15		29

sum = 15/7 + 15/10 = 2 + 1 = 3 

 

n보다 작기 때문에 

 

min = mid+1 = 16

 

min		mid		max
16		22		29

 

sum = 22/7 + 22/10 = 3 + 2 = 5 

 

n보다 작기 때문에

 

min = 22 + 1 = 23

 

min		mid		max
23		26		29

 

sum = 26/7 + 26/10= 3+2 = 5

 

n보다 작음

 

min = 26 + 1 = 27

 

min		mid		max
27		28		29

 

sum = 28 / 7 + 28 / 10 = 4 + 2 = 6 

 

n과 같음 

 

answer = 6

 

min = 28 - 1 = 27

 

min		mid		max
27		27		27

 

 sum = 5

 

n보다 작음 

min은 mid + 1 = 28 인데 

 

max 값을 넘겨버려서 

더 이상 반복문이 돌지 못함

 

이런 느낌일까?