99클럽 코테 스터디 3일차 TIL 이분탐색(입국심사)

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

프로그래머스

 

시간의 최솟값을 구해야하고, 범위로 알 수 있듯 이분탐색 문제였다.

문제를 읽으면서 우선 시간을 mid로 설정하고 구하면 되겠다 싶었는데, 문제는 조건을 어떻게 설정하냐 였다.

주어신 심사대에서 처리 가능한 인원수 = 현재 주어진 시간(mid) / 각 심사대에서 걸리는 시간 을 이용하면 되는 문제였다.

(즉, 만약 30시간이 걸린다고 했을 때 주어진 테케에서는 1번 심사대: 30/7 = 4.XX명, 2번 심사대: 30/10 = 3명으로 최대 7명 처리 가능한 것이다.)

 

이렇게 구현해서 제출했으나 히든테케의 절반이 틀렸고, 확인 결과 자료형으로 인한 오버플로우 문제였다.

따라서 int의 범위를 넘어갈 것 같은 부분들을 long으로 다 변경해주었더니 통과 했다!

 

<제출 코드>

import java.util.*;

class Solution {
    
    static long answer = Long.MAX_VALUE;;
    static int len;
    
    public static void binarySearch(long start, long end, long n, int[] times){
        if(start > end) return;
        long mid = (start + end) / 2;
        
        long num = 0;
        for(int i=0; i<len; i++){
            num += mid / times[i];  // 해당 예상 시간에 따른 처리 가능한 인원 수 계산
        }
        if(num >= n) {
            answer = Math.min(answer, mid);
            binarySearch(start, mid-1, n, times);
        }
        else binarySearch(mid+1, end, n, times);
    }
    
    public long solution(int n, int[] times) {
        
        len = times.length;
        
        Arrays.sort(times);
        binarySearch(1, (long)n*times[len-1], n, times);
        
        return answer;
    }
}