알고리즘

프로그래머스 입국심사 (JAVA)

박카스마시며코딩 2022. 6. 21. 17:01

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

 

코딩테스트 연습 - 입국심사

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한

programmers.co.kr

 

저는 이분탐색을 통해 문제를 해결하였습니다.

이분 탐색을 통해 해당 시간이 해당 인원을 검사할 수 있는지 판단하였습니다.

해당 인원을 검사할 수 있는 시간이 된다면 end를 줄이고, 검사할 시간이 안된다면 start를 늘려가면서 검사에 필요한 최소 시간을 찾아나갔습니다.

 

class Solution {
    public long solution(int n, int[] times) {
        long answer = binearySearch(n,times);
        return answer;
    }
    private static final long START_TIME = 1L;
    private static final long END_TIME = 1_000_000_000L * 1_000_000_000L;
    private long binearySearch(int n,int[] times){
        long start = START_TIME;
        long end = END_TIME;
        long result = 0;
        while(start <= end){
            long mid = (start + end) / 2;
            if(checkInTime(n,times,mid)){
                result = mid;
                end = mid -1;
            }else{
                start = mid +1;
            }
        }
        return result;
    }
    private boolean checkInTime(int n , int[] times, long totalTime){
        long cnt = 0;
        for(int time : times){
            cnt += totalTime / time;
        }
        if(cnt >= n){
            return true;
        }else{
            return false; 
        }
    }
}