[프로그래머스(Programmers)] 입국심사 (java, 이분탐색)

안녕하세요! 오늘은 프로그래머스의 입국심사 문제를 풀어보겠습니다 (❁´◡`❁)

문제링크

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

문제 풀이

1. 이진탐색(binary search) 이용

이진탐색을 이용해 푸는 문제입니다. 탐색할 대상은 총 소요 시간이며, 총 소요시간을 times배열로 나누었을 때 값이 n보다 크면 시간이 덜 필요하므로 right = mid -1이 되고, n보다 작으면 시간이 더 필요하므로 left = mid+1이 됩니다.

2. 중요 함수 설명

1) binarySearch: 이진탐색을 수행하는 함수

static long binarySearch(int[] times, int n, long max){
        //이진탐색을 수행하는 데 필요한 left, right, mid 변수 선언
        long left, right, mid;
        long ans;
        
        while(right가 left보다 클 때){
            mid = (left+right)/2;
            if(mid시간동안 심사할 수 있는 사람 수가 n보다 많다면){
               ans = mid와 ans 중 더 작은 값
               right = mid - 1; 
            } else{   //mid시간동안 심사할 수 있는 사람 수가 n보다 적다면
               left = mid + 1;
            }
        }
        
        return ans;
    }

2) needsMoreTime: mid시간이 걸리면 몇명을 심사할 수 있는지 계산

전체 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        
        return binarySearch(times, n, times[times.length-1]);
    }
    
    static long binarySearch(int[] times, int n, long max){
        long left = 0;
        long right = n*max;
        long mid = 0;
        long ans = Long.MAX_VALUE;
        
        while(left <= right){
            mid = (left+right)/2;
            if(needsMoreTime(times, mid, n)){    //시간이 덜 필요
                ans = ans > mid ? mid : ans;
                right = mid - 1; 
            } else{                             //시간이 더 필요
               left = mid + 1;
            }
        }
        
        return ans;
    }
    
    //시간이 더 필요한지, 덜 필요한지 계산하는 함수
    static boolean needsMoreTime(int[] times, long mid, int n){
        long passedAmount = 0;
        
        for(int i=0; i<times.length; i++){
            passedAmount = passedAmount + mid/times[i];
        }
        
        if(passedAmount >= n)   return true;    //시간이 덜 필요함
        else                   return false;    //시간이 더 필요함
    }
}

[참고한 곳]
https://velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC-Java