[프로그래머스][Kotlin][이분탐색]입국심사

해당문제는 이분탐색을 알고 있다면 간단하게 풀 수 있는 문제였습니다. 

아이디어로는 임의값(시간)내 심사가 가능한지 확인 하는 것입니다.(시간 내 모든 심사가 가능한지)

문제를 확인해보면

제한사항

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

상기내용을 보면 최악의 케이스인 경우 1,000,000,000분 동안 심사하는 심사관 1명, 1,000,000,000명 의 입국심사를 기다리는 사람이 있을 수도 있습니다.

그렇다면 최대 걸리는 시간은 1,000,000,000 * 1,000,000,000 이란 것을 알 수 있습니다.

최소는 1분동안 심사하는 심사관과 1명의 입국심사를 기다리는 사람 등이 있음을 알 수 있습니다.

그렇다면 최소 걸리는 시간은 1*1 입니다.

 

※막간 이분탐색 간단 설명

이분탐색의 개념은 정답이 될 수 있는 수들 중 최솟값과 최댓값 사이 중간값을 확인하여 최적해를 찾아 내는 개념입니다.

예시로 술게임 중 소주뚜껑에 적혀있는 번호를 맞추는 것과 같습니다. 단 다른 조건 하나는 해당 값이 맞더라도 그 수는 정답이 될 수 있고 그 수 보다 작다라고만 말하는 것입니다. 그렇다면 최적의 해는 최솟값이 결국 최대값보다 작으면서 최대의 작은수(?) 가 되어야 합니다.

아래 예시를 들어보겠습니다. 

 

ex) 1~50 중 1개의 수 (37)

(최소값+최대값) / 2 = 중간값

(1      +    50) / 2 = 25 (소수점 버림) up

(26    +    50) / 2 = 38 down (만약 중간 값이 작을 경우 최솟값을 중간값+1 로 만들어 줍니다.

                                     +1를 하는 이유는 이미 중간값보다 크다는 것을 알았기 때문입니다. )

(26    +    38) / 2 = 32 up (만약 중간 값이 클 경우 최대값을 중간값으로 만들어 줍니다.)

(33    +    38) / 2 = 35 (소수점 버림) up

(36    +    38) / 2 = 37 down (해당수가 정답이지만 최소값이 최대값보다 작기에 추가 진행)

(36    +    37) / 2 = 36 (소수점 버림) up

(37    +    37) / 2 = 37 (정답) // 위에서 말한 조건을 모두 완료 하였으므로 끝)

 

상기 예시를 코드로 작성해보겠습니다.

 

val sojoNum = 37
    
    fun main(){
        var max = 50
        var min = 1
        
        while(max > min){
            var mid = (max + min)/2
            if(check(mid)){
                max = mid
            } else {
                min = mid+1
            }
        }
        println(min) // 37
    }
    
    fun check(mid: Int): Boolean {
        return sojoNum <= mid
    }

 

상기 예시와 방법대로 해당 문제의 코드를 작성해보겠습니다.

상기와 다른 점으로는 (임의의 값(mid)/times의 값(소수점 버림)) 들의 합이 N을 넘기는지 체크 하며 해당하는 값들 중 최적해를 찾아내는 것입니다.

 

하기는 작성한 코드와 실행 결과 입니다.

class Solution {

    var N: Int? = null
    lateinit var Times: IntArray

    fun solution(n: Int, times: IntArray): Long {
        N = n
        Times = times
        var maxValue = 1000000000L * 1000000000L
        var minValue = 1L
        while(maxValue > minValue){
            var midValue = (maxValue + minValue)/2L
            if(check(midValue)){
                maxValue = midValue
            } else {
                minValue = midValue+1L
            }
        }
        return minValue
    }

    fun check(mid: Long):Boolean{
        var num = 0L
        Times.forEach{
            num += (mid / it.toLong())
        }
        return N!!.toLong() <= num
    }
}

테스트 1 〉	통과 (0.11ms, 62.5MB)
테스트 2 〉	통과 (0.37ms, 61MB)
테스트 3 〉	통과 (1.84ms, 61.7MB)
테스트 4 〉	통과 (53.05ms, 63.6MB)
테스트 5 〉	통과 (56.77ms, 64.6MB)
테스트 6 〉	통과 (56.73ms, 63.7MB)
테스트 7 〉	통과 (55.95ms, 63.8MB)
테스트 8 〉	통과 (53.72ms, 64.8MB)
테스트 9 〉	통과 (0.10ms, 59.3MB)