[프로그래머스 스터디 6주차] 이분탐색 입국심사 Lv.3 - 파이썬(Python)

📑 문제

https://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명 이하입니다.

입출력 예

n/ times/ return

6

[7, 10]

28

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

 

 

 

 

 

 

✒️ 풀이

 심사관이 심사하는데 걸리는 전체 시간을 이분탐색 해나가는 문제이다.

 

◻️ 처음에는 가장 오래 걸리는 시간(심사를 가장 오래하는 사람이 모든 인원을 심사한다고 할 때)을 기준으로 하여, 루프를 돌 때마다 low/high 를 좁혀가며 조절한다.

◻️ 각 심사원마다 기준시간 동안 몇 명을 심사할 수 있는지(기준시간//심사시간) 총 합을 구한다.

◻️ 합이 n보다 많으면, 기준 시간 안에 모든 이를 충분히 심사할 수 있다는 뜻이므로 최적의 시간을 위해 high를 좁혀서 다시 탐색해본다.

◻️ 합이 n보다 작으면, 기준 시간동안 모든 이를 심사할 수 없다는 뜻이므로 low를 높여서 전체 심사시간을 늘려본다.

 

 

 

 

 

 

 

 

 

🙋‍♀️ 의견

 어려워서 문제를 이해하고 접근하는데 시간이 꽤 오래 걸렸다 (ㅠㅠ)

 이분탐색으로 풀긴 했지만 이분탐색으로 안느껴진다 해야하나.................?

 이분탐색으로 구한 최적의 심사시간이라면, 빠르게............심사가 되나보다

 

 

 

 

 

 

 

 

💻 소스코드: 파이썬(Python)

def solution(n, times):
    answer = 0
    low = 0
    high = max(times) * n   # 모든 인원 검사에 최대로 걸리는 시간

    while low <= high:

        # 입국심사 최소 시간
        # 처음에는 가장 오래 걸리는 심사관의 시간과 가장 적게 걸리는 심사관의 시간의 평균으로
        mid = (low + high) //2

        count = 0
        for time in times:
            count = count + mid // time

            # 모든 인원을 검사 가능 하면 break
            if count >= n:
                break

        # 모든 인원을 검사 가능하면 answer를 지금으로 업데이트 해주고
        # 최소 시간을 줄여나간다. high가 줄어들 수 있는 이상 최소값이 더 있을 수 있다.
        if count >= n :
            high = mid - 1
            answer= mid
        # 모든인원을 검사 할수 없으면 최소 시간을 늘린다.
        else :
            low = mid +1

    return answer

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨