[프로그래머스 lev3/JS] 입국심사

문제 출처

프로그래머스 lev3 - 입국심사

나의 풀이(실패)

다른 풀이

이분탐색 유형.

• n이 최대 10억이고, 심사관의 숫자가 최대 10만이므로
  O(n)도 위험할 수 있다. => O(logn)인 이분탐색을 고려해야 한다.
• 이분탐색을 하려면 먼저, 가능한 정답 중 최소값과 최대값을 먼저 찾아서 left, right으로 각각 배치한다.
  그리고 mid 값으로 계산을 하며 가능한 정답들을 줄여나가다가
  left > right가 되는 시점에 while문을 종료시키고 답을 도출하면 된다.
• 시작값은 최대값으로 설정한 뒤, 최소값을 찾아 나선다.

모든 사람들이 심사 받는 게 판단 조건이다. 이중에서 심사 시간을 줄이는 게 목적이므로, cnt 변수를 통해 심사 받은 사람의 숫자를 센다.
그리고 모두가 심사를 받은 시점(cnt가 n보다 크거나 같아지는 시점)에 mid와 answer를 비교해 최소값을 업데이트해나간다.

• 이분탐색에서는 정답 후보 중에서 최소값과 최대값을 설정해놓는 게 중요하고, 그 다음으로 판단 조건(정답 후보들의 필요조건)을 찾는 게 중요하다.
• 여기서의 판단 조건은 최소값을 찾는 로직이 아니다. 가장 작은 정답 후보값부터 가장 큰 정답 후보값까지, 모두가 충족해야 하는 가장 포괄적인 로직을 찾는 것이다. 그 포괄적이고 공통적인 최소한의 로직을 통과하면 최대값을 줄이고, 통과하지 못하면 최소값을 줄여나가는 방식이다. 최소값은 판단 조건으로 찾는 게 아니라 범위를 줄여가며 찾는 것이다. 판단 조건 하나로 최소값을 찾는 게 아니라, 느슨하지만 필수적인 그 로직과 함께 범위를 줄여나가며 값을 찾는 것이기에 로직 자체를 너무 복잡하게 구현하려 하면 꼬이기 쉽다.
• 이 문제에서는 모든 사람들이 심사를 받는다는 사실이 판단 조건이 된다. 도출한 mid 값으로 모두가 심사를 받을 수 있다면 최대값을 줄이고, 심사를 받을 수 없는 mid 값이라면 최소값을 증가시켜 값을 찾는다.

현재 mid 값으로 모든 사람을 심사할 수 있다면(cnt>=n), right 값을 mid-1 값으로 당겨서(범위를 좁혀서) 더 적은 시간으로 심사할 수 있는지 판단한다.

반대로, 현재 mid 값으로 모든 사람을 심사할 수 없다면, 보다 많은 시간이 필요하다는 의미이므로 left 값을 mid+1로 당긴다.

function solution(n, times) {
  times.sort((a,b) => a-b)
  let left = 1
  let right = n * times[times.length -1]
  let answer = right // 최대값으로 설정하고 시작 

  while(left <= right){
    let mid = Math.floor((left + right) / 2)
    let cnt = 0
    times.forEach(value => {
      cnt += Math.floor(mid / value) // 검사관 한 명이 최대 몇명까지 검사할 수 있는지 
      if(cnt >= n) {
        answer = Math.min(mid, answer) // 최소값으로 업데이트 
        return
      }
    })
    if (cnt >= n) right = mid - 1
    else left = mid + 1
  }
  return answer
}

console.log(solution(6, [7, 10])) // 28 

위 코드를 축약하면 아래와 같다.

function solution(n, times) {
  let min=0 
  let max= n * Math.max.apply(null, times)
  
  while(min<=max){
    let mid = Math.floor((min+max)/2)
    let maxInMid = times.reduce((acc,cur) => acc += Math.floor(mid/cur), 0)
  
    if(n <= maxInMid) max = mid - 1
    else min = mid + 1 
  }
  
  return min 
}

참고

[프로그래머스 level3] 입국심사 javascript