프로그래머스 - 입국심사

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

n	times	return
6	[7,10]	28

입출력 예 설명

• 가장 첫 두 사람은 바로 심사를 받으러 갑니다.
  7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
• 10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
• 14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
• 20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

---

이분탐색을 이용하여 시간복잡도를 줄여본다.
시간이 각 [7,10]분 걸리는 심사관 2명이 있을 때 검사를 할 수 있는 최소한의 시간을 찾는것.
검사하는데 최대로 걸리는 시간은 10 * 6 = 60 분이 걸린다.

• 60분일 시 검색대에서 검사 할 수 있는 사람의 수
  7 : Math.floor(60 / 7) = 8명
  10 : Math.floor(60 / 10) = 6명
  8 + 6 = 14 이므로 검사 해야하는 사람의 수보다 많다.

• 시간을 1에서 60사이의 중간으로 줄인다(심사하는데 걸리는 시간이 최소 1분 이상이므로)
  Math.floor((1 + 60) / 2) = 30
  30분일 시 검색대에서 검사 할 수 있는 사람의 수
  7 : Math.floor(30 / 7) = 4명
  10 : Math.floor(30 / 10) = 3명
  4 + 3 = 7이므로 검사 해야하는 사람의 수보다 많다.

• 시간을 1에서 29사이의 중간으로 줄인다(30분일 시 검사해야하는 사람의 수보다 많으니까, 30초는 되지 않았으니 30 - 1)
  Math.floor((1 + 29) / 2) = 15
  30분일 시 검색대에서 검사 할 수 있는 사람의 수
  7 : Math.floor(15 / 7) = 2명
  10 : Math.floor(15 / 10) = 1명
  2 + 1 = 3이므로 검사 해야하는 사람의 수보다 적다.

• 시간을 16에서 30사이의 중간으로 줄인다(15분일 시 검사해야하는 사람의 수보다 적으니까)
  Math.floor((16 + 30) / 2) = 23
  30분일 시 검색대에서 검사 할 수 있는 사람의 수
  7 : Math.floor(23 / 7) = 3명
  10 : Math.floor(23 / 10) = 2명
  3 + 2 = 5이므로 검사 해야하는 사람의 수보다 적다.
  . . .

이렇게 반복하다 보면 원하는 검사인원에 맞는 시간을 찾을 수 있게 된다

문제풀이 1

function solution(n, times) {     
    times = times.sort((a,b) => a-b); // 오름차순으로 숫자 정렬
              
    let left = 1;      // 최소 시간 1분
    let right = n * times[times.length-1];  // 최대 시간
    let middle 
    let count 
    
    while (left <= right) {
        middle = Math.floor((left + right)/2); // 최대값에서 반을 나눈다.          
        count = times.reduce((acc ,curr) => {
            return acc + Math.floor(middle / curr)
        },0) // 심사관이 총 검사 할 수 있는 인원 수 

        if(count > n) { // 제한인원보다 더 많이 검사 할 수 있으면
            right = middle - 1 // middle값에서 - 1
        } else if(count < n) {
            left = middle + 1
        } 
        if(count === n) { // 제한인원과 맞다면 시간을 리턴
            return middle 
        }
    }
}

문제풀이 1에서는 solution(6, [7, 10])의 경우 테스트 케이스를 통과하지만, 나머지 테스트케이스의 경우 통과하지 않는다. 이 경우 최솟값을 찾는 것이 아니라 count가 n과 맞기만 한다면 결과값을 도출하기 때문. 따라서 최솟값을 찾아낼 수 있도록 수정해야 한다.

문제풀이 2

function solution(n, times) {     
    times = times.sort((a,b) => a-b);     
              
    let left = 1;      
    let right = n * times[times.length-1]; 
    let middle 
    let count 
    let answer = [] // 결과 값을 넣을 배열
    
    while (left <= right) { 
        middle = Math.floor((left + right)/2);      
        count = times.reduce((acc ,curr) => {
            return acc + Math.floor(middle / curr)
        },0) 

        if(count >= n) { // 제한인원보다 더 많이 검사 할 수 있거나 같으면
            right = middle - 1 
        } else if(count < n) {
            left = middle + 1
        } 
        if(count === n) { // 제한인원과 맞다면 시간을 answer에 push
            answer.push(middle)
        }
    }
  	return Math.min(...answer) // 최솟값을 도출
}

문제풀이 2의 경우 2개 빼고 테스트 케이스를 다 통과한다. 오버플로우를 잡아야 할 것 같은데ㅠㅠ 아직까지 머리를 굴리는 중이다