[C#] 입국심사

프로그래머스 문제

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

풀이 후기

1. 분석

더럽게 큰 숫자를 통해 이분 탐색임을 알 수 있다. 이미 이분 탐색은 더 악랄한 문제(금과 은 운반하기, https://school.programmers.co.kr/learn/courses/30/lessons/86053)에서 당할 만큼 당했기 때문에 조금은 익숙하다.

문제의 핵심은 딱히 생각하지 않아도 특정 시간안에 얼마 만큼의 사람을 처리할 수 있는가? 특정 시간을 mid 값으로 잡아서 times 배열에 있는 심사관이 숨도 안쉬고 일 했을 경우 몇 명이나 보낼 수 있는가 처리하면 되는 문제다.

그냥 평범한 이분 탐색 문제이긴 한데...

long max = times.Min() * (long)n;

이런 식으로 max를 구할거면, 기본으로 주어지는 인자에서 n은 int형이기 때문에 long으로 변환시키지 않으면 테스트 케이스가 터진다. 거의 처음 구현하는 이분 탐색임에도 더 고칠게 없어서 뭐가 잘못된거지 고민하다가 이유를 알고는 너무 허무해졌다.

max를 times min으로 잡은 이유는 오래 걸리는 심사대는 쓸 이유가 없기 때문이다. 10명, 심사관 [1, 100000]이 있으면 최대 시간은 100000*10이 맞긴 하지만, 가장 효율적인 심사관 1명이 모든 인원을 처리 했을 경우가, 실질적으로 고려할 수 있는 가장 최대 시간이기 때문에 그냥 그렇게 했다. 근데 써놓고도 뭐라고 쓴지 잘 모르겠다.

2. 실행 결과

3. 코드

using System;
using System.Linq;

public class Solution {
    public bool CanPassInTime(long time, int n, int[] times)
    {
        long people = 0;
        
        for (var i = 0; i < times.Length; i++)
        {
            people += (int)(time / times[i]); 

            if (people >= n)
            {
                return true;
            }
        }
        
        return false;
    }
    
    public long solution(int n, int[] times) {
        long min = 1;
        long max = times.Min() * (long)n;

        while (min < max)
        {
            long mid = (max + min) / 2;
            
            if (CanPassInTime(mid, n, times))
            {
                max = mid;
            }
            else
            {
                min = mid + 1;
            }
        }
        
        return max;
    }
}