[Javascript/PGS] Lv.3 : 입국심사 (이분탐색)

 

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

프로그래머스

 

---

 

프로그래머스 레벨3 문제.

문제를 보고 이진탐색으로 풀어야겠다는 아이디어를 떠올리기 어려움 ㅠㅡㅠ

 

오늘 새롭게 배운 것

js 배열에서 최댓값 찾기 : Math.max(...times)

배열 앞에 ...을 붙여야 함.

Math.max()는 배열을 직접 받을 수 없으므로 전개 연산자가 필요‼️

 

⚠️ 주의점 1.

이분탐색 후, 답이 도출되었지만 가능한 경우가 여러개 있을 수 있으므로
right-left가 충분히 작지 않다면 더 작은 수를 찾아 탐색해야 합니다. 

(예시 : left-20, mid-21, right-23 인 경우에서 답이 20과 21 모두 가능할 수 있음 -> 최솟값을 찾아야 함!)

반올림 문제인지..

이걸 놓쳐서 틀림 ㅠㅠ

질문게시판의 어느 귀인 덕분에 해결!

 

⚠️ 주의점 2.

또 고려해야 할 점은, 테케 최댓값이 크기 때문에

반복문으로 누적합을 구할 때 -> int 범위형을 넘어가지 않도록, 어느 선에서 중단시켜야 한다.

---

나의 풀이

function solution(n, t) {
    let answer = 0;
    let managers = t.length;
    let times = t.map(Number);
    // (시간 / 소요시간) 의 총합 = 심사가능한 사람 수
    
    let left = 1; let right = Math.max(...times) * n;
    console.log(right)
    let mid = 0;
    let sumPeople = 0;
    while(left <= right){
        mid = Math.floor((left+right)/2);
        for(let i=0; i<managers; ++i){
            sumPeople += Math.floor(mid/times[i]);
            if(sumPeople>n) break;
        }
        if(n === sumPeople) {
            if(right-left <= 1) return mid;
            right = mid-1;
        }
        if(n <= sumPeople) {
            right = mid-1;
            answer = mid;
        }
        else left = mid + 1;
        sumPeople = 0;
    }
    return answer;
}