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

이진 탐색의 필요성

• 문제에서 제시되는 시간, 사람 수는 최대 10억분, 10억 명이 나올 수 있기 때문에 시간복잡도를 고려하는 것이 중요하다.
• 선형 탐색은 불가능하다고 생각하면 된다. 따라서 로그 시간이 되도록 고려해야한다.
• 로그 시간을 나타내는 대표적인 알고리즘은 이진 탐색이다.
• 이진 탐색 알고리즘을 위해 정렬은 필요하지만, 제시된 times(심사관들의 시간 목록)은 최대 10만이기 때문에 선형 로그시간도 가능하다.

풀이 전략

• 특정 값을 찾는 것이 아니다.
• 최소 몇 분에 모든 심사가 전부 종료되는지? 가 목표이다.
• 이런 조건에 맞는 값을 찾는 문제의 유형을 결정 문제 라고 칭한다.
• 그리고 결정 문제를 해결하는 알고리즘을 Parametric Search 알고리즘이라 한다.

풀이 로직

• 모든 심사가 종료되는 데 걸리는 시간은 최소 1분에서 최대 10억분 * n명 이 될 것이다.
• 심사관들이 몇 명을 처리하는가? 에 대해서 알아봐야한다.
• 심사가 완료되는 입국자가 주어진 n보다 작다면, 시간을 증가시켜야하고, 입국자가 주어진 n보다 크다면, 시간을 감소시켜야한다.
• 여기서 필요한 것은, 심사관이 시간 대비 몇 명을 처리할 수 있는가? 이다.
  • 현재 시간 / 심사관 당 심사 시간의 값은 심사관 당 처리 가능한 입국자 수가 된다.

풀이 코드

function solution(n, times) {
    times.sort((a, b) => a - b)
    // 목표는 모든 입구자들이 처리되는데 걸리는 최소 "분"이다.
    // 그리고 최소 1분, 최대 times값 * n 분이 될 것이고, 이 사이에 무조건 최소 시간이 있을 것이다.
    let left = 1;   // 최소 1분
    let right = times[times.length - 1] * n // 최대 times * n 분
    
    // 위 시간의 흐름 사이에, 심사관들이 모든 입구자들을 처리하는데 걸리는 최소 시간(정답)이 존재할 것이다.
    // 이 시간을 "이진 탐색"을 이용하여 찾을 것이다.
    while(left <= right) {
        const mid = Math.floor((left + right) / 2)  //최소 "분"과 최대 "분"의 중간값
        
        // 현재 중간값(분) 에서의 심사관들이 모든 입구자들을 처리하는 걸리는 시간들의 합
        // 각 심사관당 심사 시간 대비 현재 시간에 처리 가능한 입국자 수는 (현재 시간 / 심사 시간)
        const sumOfTimes = times.reduce((acc, time) => acc + Math.floor(mid / time), 0)
        
        // 만약 현재 시간에서 모든 심사관들이 처리가능한 입국자 수가 기다리는 사람 수 n보다 작다면
        // 중간값 왼쪽은 확인할 필요가 없다. 따라서 left를 중간값 바로 다음으로 옮겨준다.
        if(sumOfTimes < n) {
            left = mid + 1
        // 오른쪽도 마찬가지로 현재 시간에서 모든 심사관들이 처리가능한 입국자 수가 기다리는 사람 수 n보다 크다면
        // 중간값 오른쪽은 확인할 필요가 없다. 따라서 right를 중간값 바로 이전으로 옮겨준다.
        } else {
            right = mid - 1
        }
    }
    // 현재 시간에서 처리 가능한 모든 입국자 수가 n보다 작을 때 left에 1을 더하고, 조건이 충족되면 반복이 종료된다.
    // 즉, 더하자마자 조건이 충족된다는 의미이다. 따라서 left(분)을 반환한다.
    // right는 조건이 충족되는 경우에도 중간값 이전으로 옮기는 작업을 한다.
    // 만약 right를 이용하여 반환하고 싶으면 + 1을 해주어야한다.
    return left
}

---

요약

< 심사를 모두 마치는데 걸리는 시간 중 가장 빨리 끝날 시간을 반환하자. >

• 이진 탐색 쓰는 이유 : n이 최대 10억, 고려해야할 시간(분)이 최대 10억이 나올 수 있기 때문에 선형시간을 통한 알고리즘은 사실상 불가능하고, 로그 시간을 고려해야하는데 대표적인 로그시간을 가지는 알고리즘이 이진 탐색 알고리즘이다.

• 풀이 로직
  1. 모든 사람이 심사를 받는데 걸리는 "시간의 최소값"을 구해야 한다.
  2. 모든 사람이 심사를 마치는데 걸리는 시간은 1분 ~ (10억 * n)분 사이에 있다.
  3. 따라서 이 시간의 범위 안에서 이진 탐색을 시행해야 한다. 선형탐색은 너무 오래 걸리기 때문이다.
  4. 이진 탐색 내 중간값에서 구한 심사를 마치는 사람의 수와 n을 비교하여 범위를 좁혀나간다.
  5. 범위가 완전히 좁혀지면, 그때의 시간을 반환하면 된다.