[프로그래머스 C#] Lv.3 입국심사

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 조건에 따라 모든 대기 인원의 입국심사를 끝내는 최소 시간을 구하는 문제

- 기다리는 사람의 범위가 10억까지 주어지는 문제이므로 최적화가 필수적이며 기다리는 사람을 기준으로 무언가를 연산하기엔 굉장히 불리함

- 심사관은 10만명 이하로 비교적 범위가 좁기 때문에 어떤 시간안에 기다리는 모든 사람의 심사가 가능한지 여부를 판단하며 시간을 기준으로 잡아 연산하는 것이 유리함

 

즉, 최소 값과 최대 값을 산정해 중간 값을 이용해 탐색을 최소화하며 최소 시간을 구함

- 중간 값이 모든 사람의 심사가 불가능 : 중간 값을 올려서 만족하는 값을 찾아야 함

- 중간 값이 모든 사람의 심사가 가능 : 중간 값을 내려서 최소 값을 찾아야 함

 

주석 참조

    using System;

    public class Solution
    {
        public long solution(int n, int[] times)
        {
            long answer = 0;
            var longArray = new long[times.Length]; // (long)times[]

            // 오름차순 정렬해서 세팅
            Array.Sort(times);
            for (int i = 0; i < times.Length; i++)
                longArray[i] = (long)times[i];
            
            // 이분탐색 기준 세팅
            long minTime = 1;
            long maxTime = (long)n * longArray[longArray.Length - 1];
            answer = long.MaxValue;

            while (minTime <= maxTime)
            {
                // 중간 값 산출 (이분탐색)
                long midTime = (minTime + maxTime) / 2;

                // 현재 midTime을 기준으로 입국심사를 끝낼 수 있는지 체크
                long count = 0;
                foreach (long num in longArray)
                    count += midTime / num;

                if (count >= n)
                {
                    // 모든 사람을 입국심사 가능한 시간
                    maxTime = midTime - 1;
                    answer = Math.Min(answer, midTime);
                }
                else // count < n
                {
                    // 모든 사람을 입국심사 불가능한 시간
                    minTime = midTime + 1;
                }
            }

            return answer;
        }
    }