[코테연습] 입국심사

 이 문제는 이분탐색 문제였다.

 

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

프로그래머스

 

 이분 탐색 문제를 확인한 후에 dfs, bfs 처럼 정해진 구현 방식을 따라 코드를 입력하였다.


 먼저 low 변수와 high 변수를 초기화한다.

 long low = 0;
 long high = ?;

 high 변수에 들어갈 수는 가장 큰 수가 들어가면 되지만, 이 문제에서 가장 큰 수를 특정하기 위해서는 times 배열의 특정 수에 n 을 곱한 값이면 될 것이다

 long high = times[0] * n;

 그 이유는 times 라는 0번째 심사관이 모든 인원 (n) 을 처리하는 시간 ( times[i] * n ) 이 가장 큰 수라고 볼 수 있기 때문이다.

 이후에는 low + 1 < high 인 조건을 만족하는 while 문을 적으면 된다.

 while( low + 1 < high ) {
 
 }

 low 와 high 를 계속 좁혀나가다가 더이상 좁힐 수 없을 때의 값이 곳 답이 되기 때문에 low + 1 < high 조건으로 반복한다.

 이제 ( low + high ) / 2 를 long mid 값으로 초기화 한다.

 while ( low + 1 < high ) {
    long mid = ( low + high ) / 2;

 }

 이제 mid 값이 위의 문제의 조건에 만족하는지 확인하면 된다.

 check(mid);

 만족한다면 어떤 mid 값이 정답에 근접했다는 뜻이며, 더욱 범위를 좁히기 위해 high = mid 로 변경한다.
 만족하지 않는다면 어떤 mid 값이 정답에 근접하지 못했다는 뜻이며, 밑에서 범위를 좁이기 위해 low = mid 값을 변경한다.
 즉 업 다운 게임처럼 check() 를 구현한다.

 이후 low+1 == high 가 되는 순간 high 의 값이 정답이 된다. 해당 코드를 구현하면 다음과 같다.

 public long solution(int n, int[] times) {

        long answer = 0;

        long low = 0;

        long high = (long) times[0] * n;

        //0, 42, 21

        //21/7 = 3, 21/10 = 2

        while (low + 1 < high){

            long mid = (low + high)/2;

            if (check(n, mid, times)) {

                high = mid;

            } else {

                low = mid;

            }

        }

        return answer;

    }

    boolean check(int n, long mid, int[] times){

        long sum = 0;

        for (int i = 0; i < times.length; i++) {

            sum+=mid/times[i];

            if (sum > n) {

                break;

            }

        }

        if (sum >= n) {

            return true;

        }

        return false;

    }