<Lv.3> 입국심사 (프로그래머스 : C#)

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

📕 문제 설명

모든 사람이 입국 심사를 받을 때 입국 심사에 걸리는 최소 시간 반환하기

1) 각 심사대마다 입국 심사가 걸리는 시간이 다름

2) 한 심사대에서는 동시에 한 명만 심사를 할 수 있으며, 더 빨리 끝나는 심사대가 있다면 기다렸다가 거기서 심사를 받을 수 있음

• Input
  입국 심사를 기다리는 사람 수 n, 각 심사관이 심사하는데 걸리는 시간 times
• Output
  입국 심사에 걸리는 최소 시간

예제

풀이

전체 시간을 이분탐색으로 확인하는 방식
1) 가장 짧게 걸리는 시간을 left, 가장 길게 걸리는 시간을 right로 설정
2) 현재 mid일때 모든 사람을 심사할 수 있다면 right를 mid 앞으로 땡기고 그렇지 않다면 left를 mid 뒤로 땡긴다. => 반복해서 최소 시간 찾기

using System;

public class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Array.Sort(times);
        
        long start = times[0];
        long end = times[times.Length - 1] * (long) n;
        long mid = 0;
        long num = 0;
        
        while (start <= end)
        {
            mid = (start + end) / 2;
            num = 0;
            foreach(int time in times)
            {
                num += mid / time;
                if (num >= n) break;
            }
            
            if (num >= n)
            {
                answer = mid;
                end = mid - 1;
            }
            else
            {
                start = mid + 1;
            }
        }
        
        
        return answer;
    }
}

결과