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

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

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

1. 유형

이분탐색

 

2. 시뮬레이션

이분탐색과 수학적 지식이 있어야 풀 수 있는 문제다.

우선 시뮬레이션일 돌려보자.

 

그렇다면 위의 과정에서 28은 어떻게 구해야할까. 이분탐색이다.

 

로직

1. 먼저 head, tail의 초기값을 설정
2. head가 tail보다 커질때까지 반복문을 돌린다
3. 조건에 따라 mid값을 변경해준다.

3. 코드

class Solution {
    public long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE;
        long head = 1;
        long tail = (long)n*1000000000;
        long mid = 0;
        while(head <= tail){
            mid = (head+tail)/2;
            long ret = calc(mid, times);
            if(ret >= n){
                tail = mid - 1;
                answer = Math.min(answer, mid);
            }else{
                head = mid + 1;
            }
        }
        return answer;
    }
    static long calc(long mid, int times[]){
        long ret =0;
        for(int time: times){
            ret += (mid/time);
        }
        return ret;
    }
}