[99클럽 코테 스터디 3일차 TIL] 입국심사 - 프로그래머스

코테 스터딜 3일차 문제는 프로그래머스의 입국심사 문제다.

마참내 이분탐색 코드를 사용했다.

 

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

프로그래머스

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다.
각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다.
한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.
가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다.
하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n,
각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 
모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

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

풀이접근

처음 문제를 읽고 감이 전혀 안잡혔다.

어디에 이분탐색 로직이 들어갈지 최대, 최소의 기준을 어떻게 잡을지 고민했다.

몇가지 테스트 케이스 만들고, 손으로 직접 풀다보니 최대값을 구할 수 있었다.

var range = (1, 0, times.max()!*n) // (left, mid, right)
range.1 = range.0 + (range.2 - range.0) / 2

이분탐색으로 범위를 좁혀나가면서

각 심사대마다 해당 시간에 심사 가능한 최대 수를 합한다.

단, 합하는 과정에서 Int 범위를 넘어설 수 있기 때문에 적절히 조건문을 넣었다.

var nums = 0
for t in times {
    if Int.max - num < range.1 / t {
        num = Int.max
        break
    }
    num += (range.1 / t)
}

 

최종적으로 n을 만족하는 최소 값을 구하는 것이다.

nums와 n의 대소 비교와 범위 재설정은 다음과 같이 한다.

if num >= n {
    range.2 = range.1
} else {
    range.0 = range.1 + 1
}
range.1 = range.0 + (range.2 - range.0) / 2

최종코드 - Swift

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var range = (1, 0, times.max()!*n)
    range.1 = range.0 + (range.2 - range.0) / 2
    while range.0 < range.2 {
        var num = 0
        for t in times {
            if Int.max - num < range.1 / t {
                num = Int.max
                break
            }
            num += (range.1 / t)
        }
        if num >= n {
            range.2 = range.1
        } else {
            range.0 = range.1 + 1
        }
        range.1 = range.0 + (range.2 - range.0) / 2
    }
    return Int64(range.1)
}

최종코드 - Python3

구조적으로 동일하지만, 정수범위가 넘어가는 것을 방지할 필요는 없다.

def solution(n, times):
    tRange = [1,0,max(times)*n]
    tRange[1] = tRange[0] + ((tRange[2] - tRange[0]) // 2)
    while tRange[0] < tRange[2]:
        nums = 0
        for t in times:
            nums += tRange[1] // t
        if nums >= n:
            tRange[2] = tRange[1]
        else:
            tRange[0] = tRange[1] + 1
        tRange[1] = tRange[0] + ((tRange[2] - tRange[0]) // 2)
    return tRange[1]

Conclusion

드디어 3일만에 이분탐색 키워드 문제에 이분탐색을 사용했다.

사실 Python 코드에서 nums의 최대값을 10^18 로 했으면 조금더 빨랐을까 하는 생각이 든다.