[알고리즘] 이분탐색을 이용한 '입국심사' 알고리즘 해결 팁

이분탐색 알고리즘에 대한 설명과, 문제 해결 방안에 대해 설명하기 전 먼저 문제는 아래에 가면 볼 수 있다.

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

이분탐색이란  ?

흔히 생각할 예시로는 Up & Down 게임을 생각하면 된다.

A라는 사람이 1 ~ 100중에 숫자를 생각할테니 맞춰보라 하였을 때 가장 빠르게 찾을 수 있는 방법은 범위중 최소값과 최대값을 더한 후 반으로 나눠 그곳을 부르는 것 이다.

(1 ~ 100이니 1 + 100 = 101,  101 / 2 = 50, 그럼 50을 부르고 Up & Down을 확인하면 된다. 이 후에는 50 + 100 = 150 /  2 = 75를 부르는 것.)

 

이처럼 범위 내에서 반씩 짤라서 탐색하는 것을 이분탐색이라고 한다.

 

위 알고리즘의 구현은 상당히 간단하다.

가장 먼저 예시를 들어보면, 아래 배열이 있다고 하였을 때 원하는 수를 찾는 것에 대한 알고리즘이다.

Array : [1, 52, 24, 31, 39]

Target : 24

 

먼저 탐색할 범위를 반드시 정렬 해야 이 알고리즘을 사용할 수 있다.

Sorted Array : [1, 24, 31, 39, 52]

 

여기서 배열의 중간 값을 구해야한다.

mid : 0 + 5(SortedArray.size) / 2 = 2

 

이 중간값의 숫자와 내가 찾고자 하는 숫자를 비교하여 왼쪽으로 탐색할지, 오른쪽으로 탐색할지에 대한 알고리즘이다.

가운데의 값은 '31'(SortedArray[2])이니, 내가 찾고자 하는 숫자보다 크기때문에 왼쪽에 있을 것이라고 생각할 수 있다.

그렇다면 이번에는 mid를 아래와 같은 식으로 바꾼다.

mid : 0 + 2(mid 값) / 2 = 1

...

 

이런식으로 계속 똑같은 처리를 반복 해주면 된다.

 

저 문제를 처음 마주했을 때 이거를 어떻게 이분탐색으로 풀지에 대한 접근이 막막하다.

접근을 위한 팁을 주자면, 이분 탐색중 나온 MID의 값으로 모든 심사관(times)에 대입했을 때 몇명을 심사할 수 있는지를 찾으면 된다.

문제에 적혀있는 대로 예시를 들면 아래와 같다.

 

n = 6

times = [7, 10]

 

min = 1

max = (10 * 6) / 2

mid = (min + max) / 2

 

라고 했을 때 MID는 30이 나오게 된다.

이 30분이 주어졌을 때 두 심사관은 최대 몇명을 구할 수 있는지 보고, OVER되면 MAX를 줄이고, 부족하면 MIN을 늘리는 형식으로 가면 된다.

 

MID가 30분이니, times별로 나눠보면 첫번째 심사관(심사하는데 7분 소요)은 30분동안 4명, 두번째 심사관(심사하는데 10분 소요)은 3명을 처리할 수 있다.

이러면 7명이나 처리할 수 있는데 문제에서는 6명을 처리하라고 하니, 이를 줄여야한다.(즉 30분보다 적은 수로 다시 찾으면 됨.)

 

문제에 대한 답을 알려주는 것 보다는 처리 방법 및 접근 방법을 적어놓는게 나중에 봤을 때 기억이 더 잘 날 것 같아서, 연습이 잘 될 것 같아서 답을 써놓진 않겠다.

 

주의할점은 시간관계도와 자료형별 숫자를 잘 보면 풀 수 있다.

혹시 이분탐색을 이용해 문제를 해결했으나 1,2,9번은 맞고 3번부터 실패할 때 아래의 값을 넣어서 테스트해보면 이유를 알 수 있을 것이다.

val n = 3L
val times = intArrayOf(1000000000, 1000000000, 1000000000)

이분탐색의 기본 알고리즘(재귀함수로 구현)

fun binarySearch(numberArray: IntArray, findNumber: Int, low: Int, max: Int): Int {
    if(low > max) {
        return -1
    }
    val mid = (low + max) / 2
    
    return when {
        numberArray[mid] == findNumber -> {
            mid
        }
        numberArray[mid] < findNumber -> {
            binarySearch(numberArray, findNumber, mid+1, max)
        }
        else -> {
            binarySearch(numberArray, findNumber, low, mid-1)
        }
    }
}

 

 

주의할 함정은 과연 꼭 정렬을 해야하는가, max와 min을 꼭 1씩 줄여야하나. 를 생각해보면 답이 나온다.

난 생각보다 헤맸다.

 

아래 더보기는 혹시 정말 모르겠으면 참고할 정답이다.

정답

fun main() {
    // 모두 toLong() 시켜야함.
    val n = 3L
    val times = intArrayOf(1000000000, 1000000000, 1000000000)

    //sorted를 하는거보다 시간관계도가 작은 min과 max를 구함.
    var min = times.min()!!.toLong()
    // max * n / times.size를 하는 이유는 max * n을 하게 되면 한명의 심사관이 모두 처리했을 때인데,
    // 가장 처리시간이 긴 사람을 기준으로 잡고 그걸 모든 심사관에게 부여하는 것.
    var max = ((times.max()!! * n) / times.size)
    
    var answer = max
    
    while(min <= max) {
        val mid = ((min + max) / 2)
        var possiblePeopleCount = 0L
        
        for(time in times) {
            possiblePeopleCount += mid / time
            
            // 심사관 별 처리 가능한 사람들의 머릿수를 구하다가 N을 넘어가게 되면 해당 MID 값을 답으로 체크해놓고 MAX를 MID - 1 처리하여
            if(possiblePeopleCount >= n) {
                answer = mid
                max = mid - 1
                break
            }
        }

        if(possiblePeopleCount < n) {
            min = mid + 1
        }
    }
    print(answer)
}