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

문제: 입국심사

---

프로그래머스

 

풀이

---

func solution(_ n:Int, _ times:[Int]) -> Int64 {

    var left: Int64 = Int64(0) // 최소 시간
    var right: Int64 = Int64(times.max()! * n) // 최대 시간
    var mid: Int64 = Int64((left + right) / 2)
    
    while(true) {
        // mid분당 처리할 수 있는 사람 수
        let people:Int64 = times.reduce(0) { Int64($0) + mid / Int64($1) }

        // 목표하는 사람 수(n) 보다 처리 가능한 사람수가 많거나 같은 경우
        if people >= n {
            right = mid - 1
        } 
        // 목표하는 사람 수(n) 보다 처리 가능한 사람수가 적은 경우
        else {
            left = mid + 1
        }
        
        // left가 right를 넘으면 이진 탐색 완료
        if right < left {
            break
        }
        
        mid = (left + right) / 2
    }
    
    // 최소 시간보다 1적은 값을 가리키고 있으므로 +1
    return right + 1
}

해당로직에서 right에 들어갈 수 있는 최댓값은 최대인원*최대심사시간이므로  1,000,000,000 *  1,000,000,000 = 1,000,000,000,000,000,000입니다. 따라서 Int32로는 표현할 수 없습니다. 

- Int64 최대: 9,223,372,036,854,775,807
- Int32 최대: 2,147,483,647

Swift에서 Int는 실행 환경에 따라 달라지는데, 찾아보니 현재 아이폰과 같이 작은 환경도 대부분 64비트로 동작한다고 합니다. 따라서 대부분의 환경에서 따로 형변환을 안해도 Int형이 Int64로 동작하므로 별도의 형변환 과정이 필요하지 않습니다. 위 코드에서도 형변환 과정을 모두 빼고도 돌려봤는데 정상적으로 통과가 되었습니다. 그러나 웹 IDE라 환경을 보장할 수 없어 안전하게 처리하기 위해 Int64를 반환값으로 사용한 것 같습니다.

 

접근방법

이분탐색이므로 최댓값(right), 최솟값(left) 그리고 사이를 좁혀갈 기준이 필요합니다. 우선 구하는 것이 시간이므로 최대 시간과 최소 시간 사이를 좁혀나가야겠다고 생각했습니다. 따라서 right는 n명의 사람을 처리하는데 필요한 최대 시간이 되고, 최소시간을 구하고자 하는 것이므로 left는 0으로 잡아주었습니다. 그 다음 각 시간(mid)에 처리할 수 있는 최대 인원을 기준으로 오른쪽 탐색, 왼쪽 탐색을 결정하였습니다. 목표하는 사람 수에 도달하였을 때는 최소 시간을 찾을 때까지 탐색하도록 목표하는 사람 수(n) 보다 처리 가능한 사람수가 많거나 같은 경우라는 조건을 적용해주었습니다

 

 

---

이분탐색은 조건식의 이꼴 여부에 걸리는 엣지케이스를 생각하는게 까다로운 것 같습니다. 사실 이것저것 하다보면 통과가 되는 경우가 많은데...ㅎㅎ 실제 코테에서는 주어진 테스트케이스만 통과했다고 안심하면 안되겠네요 😅

 

 

감사합니다.