[프로그래머스] Lv.3 입국심사 (자바스크립트)

 

 

*모든 코드는 Javascript로 작성합니다.

*코드는 참고용으로만 봐주세요!

 

---

문제

 

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

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

 

 

 

해결방법

 

< 이분 탐색으로 해결 >

- (사람/카운터 개수)를 n이라 할 때,

- 이분 탐색의 최솟값은 가장 짧은 심사 시간 * n

- 이분 탐색의 최댓값은 가장 긴 심사 시간 * n 

- 특정 시간 안에 모든 사람을 심사할 수 있는지 여부를 알려주는 함수를 작성하기

   → (총 소요 시간 / 각 카운터 심사 시간)은 한 카운터에서 총 소요 시간 동안 심사할 수 있는 사람 수.

   → 각 카운터에 대해 계산한 값을 모두 더했을 때, 그 값이 사람 수보다 크면 해당 시간 내에 심사 가능.

 

 

 

 

코드

 

function solution(n, times) {          var counters = times.length;          var min_time = Math.min(...times)*Math.floor(n/counters);     var max_time = Math.max(...times)*Math.ceil(n/counters);          var left = min_time - 1;  * 최종적으로 right를 반환하기 때문에, 최솟값에서 1을 뺀 값으로 설정.     var right = max_time;          while (right - left > 1){         var mid = Math.floor((right+left)/2);         if (isPossibleInTime(mid)){             right = mid;         }         else {             left = mid;         }     }               function isPossibleInTime(t){         var sum = 0;         times.forEach((duration)=>{             sum += Math.floor(t/duration);         })         if (sum >= n) return true;         return false;     }               return right; }