プログラマー-入国審査

問:入国調査(解答失敗)

基本内容

均一分布による最小時間の求め方

マイコード

コード1

function solution(n, times) {
    var answer = 0;
    let isEmpty = [];
    let count;
    times.sort((a,b)=>a-b);
    for(let i=0;i<times.length;i++)
        {
            isEmpty[i] = false;
        }
    for(count = 1;;count++)
        {
            for(let j=0;j<times.length;j++)
                {
                    if(isEmpty[j] === false)
                        {
                            isEmpty[j] = true;
                        }
                    if(count % times[j] === 0)
                        {
                            isEmpty[j] = false;
                             n--;
                        }
                }
            if(n===0)
                break;
        }

    return count;
}

コード2

function solution(n, times) {
    var answer = 0;
    let value =0;
    for(let count=times[0];;count++)
        {
            for(let j=0;j<times.length;j++)
                {
                 value += Math.floor(count / times[j] )
                }
            if(value === n ){
                return count;
            }
            value = 0;
        }
}

コード1とコード2の両方にタイムアウトが発生しました.

にぶんたんさく

必要なナビゲーション範囲を2つの部分に分けて検索します.
私たちは私たちのニーズを満たす答えを見つける必要があります.だから、これらの答えを探求することでタイムアウトを解消する必要があります.

基本的な二分探索

function binarySearch (target, dataArray) {
let low = 0;
let high = dataArray.length - 1;
let index = 0;
  
while (low <= high) {
	let mid = Math.floor((high + low) / 2);
	let guess = dataArray[mid];
		if (guess === target) {
			return guess;
		} 
 	 	else if (guess < target) {
      			low = mid + 1;
    		} 
  		else {
     	 		high = mid - 1;
    		}
	index++;
	console.log(`${index}. low: ${low}, mid: ${mid}, high: ${high}, data: ${dataArray[mid]}`);
}
return undefined;
}

重要な部分

while(low <= high){
  let mid = Math.floor((high + low) /2);
  ... 어떠한 것을 통해 얻어낸 value값 (ex)배열에서의 mid를 넣었을때 얻어낸 value)
  if (value === target) {
		return value;
	} 
  else if (value > target) {
	high = mid - 1;
	} 
  else {
	low = mid + 1;
	}
}

問題コード

ある時間帯の入国審査に多くの人が通過した場合、それはその時間より短い時間であり、通過する人が少なければその時間より長い時間であり、繰り返し行われる.

function solution(n, times) {
    let value=0;
    var min =0 , max = n * Math.max.apply(null, times);
    while (min <= max) {
        var mid = Math.floor((min + max) / 2);
         for(let j=0;j<times.length;j++)
                {
                 value += Math.floor(mid / times[j] )
                }
        if( n <= value) {
            max = mid -1;
        } else {
            min = mid + 1;
        }
        value = 0;
    }
    return min;
}

 if( n <= value) {
            max = mid -1;
        } else {
            min = mid + 1;
        }

....
 return min;

上記のコードに変換する理由は、 value += Math.floor(mid / times[j] )を満たす値がnに等しい場合、最小の時間ではない可能性があるため、まずn === valueの最大値を減らすことでさらなる反復を行い、得られるからである.

なぜminなのかを返す

この部分は特に悩んでいる.どうしてmidじゃなくてminなの?
ex)
入力値〉6,[7,10]
二十八

function solution(n, times) {
    let value=0;
    var min =0 , max = n * Math.max.apply(null, times);
    while (min <= max) {
        var mid = Math.floor((min + max) / 2);
         for(let j=0;j<times.length;j++)
                {
                 value += Math.floor(mid / times[j] )
                }
         console.log(min,mid,max,value)
        if( n <= value) {
            max = mid -1;
        } else {
            min = mid + 1;
        }
        value = 0;
       
    }
    return mid;
}

console.logの結果は以下の通りです.
すなわち、見つかった値が実際の値より小さく、その後より少ない値が現れ、最小値が増加した場合、while文の終了時に正しい値が見つかったのは、その時の最小値のみである(したがってmid値を返す場合、エラーのある部分).
0 30 60 7
0 14 29 3
15 22 29 5
23 26 29 5
27 28 29 6
27 27 27 5

ifelseセクションを使用する理由

 if( n <= value) {
            max = mid -1;
        } else {
            min = mid + 1;
        }

この部分でif,else if,elseを用いて試用しないのは,n == valueを満たすnが最小値ではない可能性があるためである.例えば、戻り値が6、[7,10]であり、戻り値が29である場合、6は最小値に対応し、28では6であるため、単独で分類すべきではない.(複雑ですね)

整理する

バイナリ検索により分離に努めたが,この問題はさらにねじって値を見つけるのではなく元の成立を減算し続け,成立しない値が現れた場合にleftを増やし,当時leftが本当に成立した最小数を示すことである.

その他のバイナリ・ナビゲーション・コード

function solution(n, times) {
    times.sort((a,b)=>a-b);
    let left = 1
    let right = times[times.length-1] * n;
    while(left <= right){
        let mid = Math.floor((left+right)/2)
        let sum = times.reduce((acc,time)=>acc+Math.floor(mid/time),0);
        if(sum < n)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return left;
}

このコードがより理解しやすいのは,sum == nであっても対応する複数の値がある可能性があるため,sumに比べてn以降の同じ瞬間が最小であることである.

        if(sum < n)
            left = mid + 1;

整理する

この問題は、単純なバイナリ検索で対応する値を見つけるだけでなく、その値の最小位置を見つけることです.したがって、if(n==sum)の形では最小値が見つからず、if(n<sum)を超える時間が最小値となるので注意が必要である.

ソース

Code Playground