[Swift Algorithm] 프로그래머스 43238 입국심사

 

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

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

 

 

문제만 봐도 1,000,000,000... 10억이죠?

O(n)을 사용해도 버거운 속도일거 같네요

시간복잡도를 줄이는 쪽으로 접근해야할텐데

문제만보고 접근방법이 떠오르지않았는데

 

이문제의 카테고리가 이분탐색 이에요 ㅎㅎ

그래서 어떻게 이진탐색을 이용할까... 생각했지만 어렵더라구요

 

너무오래생각하게되면 풀이를 보고 배우는게 더좋다고했어요... ㅠㅠ

 

분을 기준으로 몇명을 검사할 수 있는지 체크하더라구요

 

풀이방법

예시기준으로

최소: 1분

최대: 주어진times의 최대 * n(사람 수) 의 시간이 걸릴거에요 -> 60

 

1 ~ 60를 이진탐색을 이용해서 찾아볼거에요

 

먼저 중간값 (1 + 60) / 2 = 30

30분이 됬을때 검사가 끝난 사람들은 몇명일까요?

30 / 7 = 4

30 / 10 = 3

 

총 7 명이죠

주어진 n은 6이기때문에 사람수가 넘어갔네요

그렇다면 더 적은 시간에 끝낼 수 있겠죠?

 

그러면 검사범위를 1 ~ 60 에서 1 ~ 29 로 줄일 수 있어요

다시 1 ~ 29의 중간값 15

15분에 검사를 끝낼 수 있는 인원은

15 / 7 = 2

15 / 10 = 1

총 3명이네요

인원이 모자라니까 더 많은 시간이 필요할 거에요

 

16 ~ 29를 비교해보고 중간값 22

22 / 7 = 3

22 / 10 = 2

총 5명

 

23 ~ 29를 비교해보고 중간값 26

26 / 7 = 3

26 / 10 = 2

총 5명

 

26 ~ 29를 비교해보고 중간값 28

28 / 7 = 4

29 / 10 = 2

총 6명으로 만족했네요!

 

여기까지는 보통 찾는 과정이맞아요

하지만

여기서 끝나면 케이스 실패를 볼 수 있어요

 

왜냐하면

인원을 만족할때 최소시간을 구해야해요

6명을 만족하지만 27분일 수도 있고 29분일 수도 있는거죠

 

현재 검사된 인원 < 주어진 검사인원(n) 일땐

시간이 더필요하겟죠?

min시간을 mid + 1시간으로 변경해주는 작업만하면돼요

 

현재 검사된 인원 > 주어진 검사인원(n) 일땐

시간을 줄여야해요

 

현재 검사된 인원 == 주어진 검사인원(n) 일땐

끝내야하나요?

아니죠 더 최소시간을 찾으러가야해요

 

따라서 

현재 검사된 인원 > 주어진 검사인원(n) 일땐

현재 검사된 인원 == 주어진 검사인원(n) 일땐

이 두케이스는 동일하게 동작하게 될거에요

 

 

 

private func solutionP43238(_ n:Int, _ times:[Int]) -> Int64 {
    let times = times.sorted()
    var maxTime = times.last! * n
    var minTime = 1
    var result = 0
    
    while minTime <= maxTime {
        let midTime = (minTime + maxTime) / 2
        var sum = 0
        times.forEach {
            sum += midTime / $0
        }
        print("mid: \(midTime), \(sum)")
        
        if sum < n { // 시간이 더필요함  mid ~ max 검사
            minTime = midTime + 1
        } else { // 인원을 만족해도 시간을 더 줄여야함 최소시간을 찾기위해서 1 ~ mid검사
            maxTime = midTime - 1
            result = midTime
        }
    }
    print(result)
    return Int64(result)
}