[Programmers] 입국 심사

🔒 문제

🧠 아이디어

심사 소요시간 (1 ~ 10억) => 일반적인 방법으로는 무조건 시간초과
심사자의 수 (1 ~ 10만) => 이걸로 뭔가 결정해야겠는데?

로 부터 힌트를 얻어야한다.

적정 time 을 이분 탐색으로 찾는데 걸리는 소요시간

time 이 10억인데 얘를

로 두면 약

이 되고

연산 회수 60회

각 라운드별 입국 심사 통과자 수 구하기

최대 10만명의 심사자에 대해

연산 회수 10만 회

Time Complexity

총 연산회수 60 * 10만 => 약 600만으로 시간 초과에 걸리지 않고 예상 종료시간을 구할 수 있다.

⚠️ 실수하기 쉬운 포인트

값의 범위가 10억 분 * 10억명 일 경우

기 때문에 Int 가 아니라 Long 으로 처리해야한다.

🔑 Kotlin Code

class Immigration {
    private fun getLowerBoundIdx(n: Long, times: List<Long>) : Long {
    // 이미 정렬된 상태므로 첫번째 값
        var left : Long = times.first()
	// 마지막 값은 최대값
        var right : Long = times.last() * n

        while (left < right) {
            val mid = (left + right) / 2
            val entranceCnt = times.sumOf { mid / it }
            if (entranceCnt >= n) right = mid
            else left = mid + 1
        }

        return right
    }

    fun solution(n: Int, times: IntArray): Long {
        val timesLong = times.map(Int::toLong).sorted()
        return getLowerBoundIdx(n.toLong(), timesLong)
    }
}