문제 : 입국심사 (풀기 실패)
기본적인 내용
골고루 분포시켜 최소한의 시간을 구하는 방법
나의 코드
코드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 모두 시간초과가 떴다.
이분탐색
원하는 탐색범위를 두 부분으로 분할해서 찾는 방식
우리가 원하는 답을 만족하는 것을 찾아내야하므로 이분탐색을 통해 시간초과를 없애보는 것
기본적인 이분탐색
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] )를 만족하는 value가 n과 같을때가 최소가 되는 시간이 아닐수도 있기 때문에 일단n === value도 max 값을 감소 시키는 것으로 반복을 더 진행하여 얻어내야하기 때문
return이 왜 min일까
이부분은 특히 고민을 많이했다. 왜 mid가 아닌 min일까
ex)
입력값 〉 6, [7, 10]
기댓값 〉 28
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결과는 아래와 같다.
즉, 실제 맞는 값을 찾아도 그보다 값을 줄인 후, 더 적은 값이 나와서 min가 증가할 경우 while문이 종료되어 그때의 min값 만이 제대로 값을 찾은 것이다(mid값은 그래서 return하면 틀린부분이 존재한다.)
0 30 60 7
0 14 29 3
15 22 29 5
23 26 29 5
27 28 29 6
27 27 27 5
if else부분을 이렇게 사용한 이유
if( n <= value) {
max = mid -1;
} else {
min = mid + 1;
}이 부분을 if , else if, else로 사용하지않고 이렇게 시용한 이유는 해당
n == value만족하는 n이 최소값이 아닐수도있기때문이다. 예를들어 6, [7,10]인데 return 값이 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)을 넘어가는 시점이 최소가 되므로 이를 주의해야한다.
출처
