프로그래머스 - 입국심사 (C#)

문제 설명

n명이 입국심사를 기다리고 있습니다.
심사관은 times.Length만큼 있고,
times에는 각 심사관이 심사하는데 걸리는 시간(분)이 있습니다.

n명이 모두 심사를 받는데 걸리는 시간(분)의 최솟값을 구하는 문제입니다.

문제 풀이

걸리는 시간의 최솟값을 구하는 문제이면서
최솟값을 구하는 시간도 최소로 해야만 합니다.
이분탐색을 이용하면 답을 금방 찾을 수 있는 문제입니다.

times를 정렬하면 times의 0번 요소가 심사를 가장 빠르게 하는 심사관입니다.
그럼 최대로 걸리는 시간은 n x times[0]입니다.

심사관이 한 명을 심사하는데 걸리는 시간은 최소 1분이기 때문에
시작하는 값(start)을 1로 끝 값(end)을 n x times[0]으로 하고,
start ~ end 사이를 이분탐색해서 걸리는 시간의 최솟값을 탐색합니다.

규칙 찾기
times가 { 6, 10 }이고, 경과한 시간이 10분일 때 심사관은 각각 1명을 처리해서 총 2명을 처리할 수 있습니다.
경과한 시간이 20분일 때 심사관은 각각 3명, 2명을 처리해서 총 5명을 처리할 수 있습니다.
그럼 현재 시간 / times[i]를 모두 더한 값은 현재 시간동안 총 몇 명을 처리했는지를 나타낸다는 것을 알 수 있습니다.

위 규칙에 따라 n은 6, times { 7, 10 }에 적용해보면
21 / 7 => 3, 21 / 10 => 2로 모든 심사관이 5명을 처리할 수 있습니다.
5명이면 입국심사를 기다리는 6명보다 적기 때문에 mid값이 지금보다 높아야 합니다.
mid값이 높아지기 위해 start를 mid만큼 올리면 다음 루틴에 현재 mid와 end 사이를 mid로 갖게 됩니다.

22 ~ 42의 mid는 33입니다.
33 / 7 => 4, 33 / 10 => 3으로 총 7이고, n보다 1이 높습니다.
총 카운트가 n이상이기 때문에 최소 시간을 현재 mid값으로 정해줍니다.
그리고 end를 현재 mid만큼 내립니다.

이렇게 중간 값을 기준으로 업, 다운을 반복하면 빠르게 탐색 범위를 좁혀 가면서 최소 시간이 몇 분인지 알 수 있습니다.

제출 코드

using System;
using System.Collections;
using System.Collections.Generic;

public class Solution 
{
    public long solution(int n, int[] times) 
    {
        Array.Sort(times);
        long[] minutes = Array.ConvertAll(times, val => (long)val);
        
        long start = 1;
        long end = (long)n * minutes[0];
        long minTime = end;
        long mid = 0;
        
        while (start <= end)
        {
            mid = (start + end) / 2;
            
            long nCount = 0;
            for (int i = 0; i < minutes.Length; i++)
            {
                nCount += mid / minutes[i];
            }
            
            if (nCount < n)
            {
                start = mid + 1;
            }
            else
            {
                minTime = mid;
                end = mid - 1;                
            }
        }        
        
        return minTime;
    }    
}