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

이분 탐색이 뭔지 한번 찾아봄

dongdd.tistory.com/50

이분 탐색 알고리즘(Binary Search Algorithm)

 

문제를 내식대로 했는데 계속 타임아웃 되길래 다른사람의 코드를 보기러 했다..

 

나는 너무 기계적으로 하나하나 어레이로 확인하고 바꾸는 방식으로 할랫는데 그냥 생각 자체를 달리 해야되네

이분 탐색을 그냥 탐색 범위를 좁혀가면서 탐색하는 방식이라고 생각하고 다양하게 사용해봐야겠다.

 

class Solution {
    fun solution(n: Int, times: IntArray): Long {
        var minTime = 1L
        var maxTime = n.toLong() * times.max()!!
        var result = maxTime
        while (minTime <= maxTime ) {
            val possibleAnswerTime = (minTime + maxTime) / 2
            val examinedPersonCount = times.fold(0L) {
                acc, eachDuration ->
                acc + possibleAnswerTime / eachDuration
            }

            if(examinedPersonCount >= n) {
                if(possibleAnswerTime < result) result = possibleAnswerTime
                maxTime = possibleAnswerTime - 1
            }
            else minTime = possibleAnswerTime + 1
        }
        return result
    }
}

이렇게 푼 풀이가 많더라. 

1) 최대 시간을 설정, 최소시간은 1로 설정

2) 예측 시간을 평균값으로 설정

3) 그 시간에 접수대를 넘어 갈 수있는 사람들수를 구함

4) 이 때 그 사람들의 수가 N보다 같거나 크다면 맥스 타임을 1 줄여서 다시 시행

N보다  민 타임을 1 증가시켜서 시행 -> 

 

접수 가능한 사람의 수가 N 보다 작다면 시간이 더 필요한 것이고 

접수 가능한 사람이 N 보다 크다면 시간이 줄어들어야 한다는것 이용한듯

 

 

5) MIN = MAX 거나 MIN > MAX가 되면 종료 됨

 

 

 

※INT/INT하면 버림을 함

1. xL 이렇게 해서 바론 LONG 타입이 되는듯.. 처음알았음