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

문제

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

프로그래머스

 

 

 

---

풀이

우선 이분탐색이 뭔지 알아야 하는 문제였다.

 

즉, 원하는 탐색 범위를 두 부분으로 분할하여 탐색하는 것이다.

 

이분(이진)탐색을 사용한 알고리즘을 처음 풀어보기 때문에 다른 블로그 해설들을 많이 참고하였다.

 

문제에서의 핵심은 한 사람이 심사대에 들어가서 입국 심사를 언제 마칠지에 초점을 두지 말고,

 

현재 시간을 기준으로 봤을 때 몇 명이 최대로 입국심사를 마칠 수 있는가? 에 집중해야 한다.

 

time 1 - 6 : 아무도 입국 심사를 마칠 수 없음
time 7 : 한 사람이 입국 심사를 마쳤기에 다른 한사람이 들어갈 수 있음.
time 8 - 9 : 아무도 입국 심사를 마칠 수 없음
time 10 : 마찬가지로 한 사람이 심사가 끝나 다른 사람이 들어갈 수 있음.
.
.
.
time 32 : 첫 번째 창구에서 4명을, 두번째 창구에서 3명을 배출할 수 있음.

 

위를 코드로 바꾸기 위해서는 여러 방법이 존재하지만 시간초과를 당하지 않으려면 이분탐색으로 문제를 풀어야 한다.

 

여기서 이분탐색을 사용하기 위해서는 ‘이분 탐색의 범위는 무엇으로 할지’ 와 ‘이분 탐색의 기준을 무엇으로 할지’로 잡아야 한다.

 

범위 : 심사를 하는데 필요로 하는 시간. 그 중 가장 비효율적인 시간이다.
      즉, 입력으로 주어지는 times 배열의 최대값과 n을 곱한 값으로 정하였다.

기준 : time배열의 값을 이분탐색의 mid값{ (최소 시간, 최대 시간) / 2 } 으로 나누고,
      나눈 값들을 sum 이라는 변수에 계속 더해나간다.

      이때, sum의 변수의 값이 n보다 크거나 같게 되면 시간이 충분했던 것이기에 시간을 줄여야한다.
      (maxTime 변수의 값을 avgTime - 1로 변경한다)

      sum 변수의 값이 n보다 작으면 시간이 부족한 것이기에 시간을 늘려야 한다.
      (minTime 변수의 값을 avgTime + 1로 변경한다)

 

위의 기준을 코드로 변경한 풀이이다.

 

class Solution {
        fun solution(n: Int, times: IntArray): Long {
        var answer: Long = 0
        var minTime: Long = 1
        var maxTime: Long = times.maxOrNull()!!.toLong() * n

        while(minTime <= maxTime){
            var avgTime: Long = (minTime + maxTime) / 2
            var sum: Long = 0

            times.forEach {
                sum += avgTime / it
            }

            if(sum >= n){
                maxTime = avgTime - 1
                answer = avgTime
            }else{
                minTime = avgTime + 1
            }
        }

        return answer
    }
}

 

위 코드에서 times.maxOrNull() 이라는 코드를 사용하였는데 ,

 

프로그래머스의 코틀린 버전은 1.6.10버전으로 array.max() 매서드가 없다…

 

내가 쓰는 코틀린 버전은 1.7을 사용하는데 1.7에는 array.max() 가 있는데 ㅠㅠ 무엇을 사용해야 할깝,,

 

---

정답

 

아직 이분탐색에 대해 잘 알지 못하고 경험이 부족하기에 열심히 문제를 보고 공부해야겠다,,,

 

 

참고 블로그 : https://blog.naver.com/gkswlcjs2/223201657964

[Java] 입국 심사