프로그래머스 입국심사 문제 (Swift 풀이)

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

프로그래머스

 

풀이 코드

import Foundation
 
func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var start: Int64 = 0
    var end: Int64 = 100000000000000000
    var temp: Int64 = 0
 
    repeat {
        var middle = ( start + end ) / 2
        var value: Int64 = 0
        times.forEach {
            value += middle / Int64($0)
        }
        if n < value {
            end = middle - 1
        } else if n > value {
            start = middle + 1
        } else if n == value {
            temp = middle
            break
        }
        temp = start
    } while start <= end
    
    var value: [Int64] = []
    times.forEach {
        value.append(temp / Int64($0))
    }
 
    var result: Int64 = 0
    for i in 0 ..< times.count {
        if result < Int64(times[i]) * value[i] {
            result = Int64(times[i]) * value[i]
        }
    }
    
    return result
}

 

풀이 과정

문제에 주어진 제한 사항을 보자.

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

10억이란 숫자가 보이자마자 이분탐색 알고리즘을 떠올렸다. 코딩테스트에서 자주 출제되진 않지만 모르고 있다면 구현하기 아주 까다로운 알고리즘이다.

이분탐색에서 체크할 로직은 단순하다. 

임의의 시간 x를 times 배열의 요소로 나눈 값들이 x라는 시간동안 각 심사관마다 처리하게 되는 사람의 수 가 된다. 이 값들을 모두 합쳤을때 문제에서 주어진 n명이 된다면 조건을 만족한다. (9줄 ~ 13줄)

다만, 문제에서 x의 최소값을 구하라고 하였으므로 위에서 언급한 방법으로 이분탐색으로 구한 시간 x에 대하여 각 심사관마다 처리하게 되는 사람의 수 를 모두 구한 뒤, 각 심사관 마다 한명을 처리하는데 걸리는 시간(times 배열의 요소)을 곱하여 모두 더하면 구하고자하는 정답이 된다. (25줄 ~ 35줄)