[JAVA] 이분탐색(이진탐색) "입국심사", "징검다리"

입국심사

 

실패코드(완전탐색방법)

class Solution {
    class Tester{
        long startT, spendT;
        Tester(long startTime, long spendingTime){
            startT = startTime;
            spendT = spendingTime;
        }
    }

    public long solution(int n, int[] times) {
        long answer = 0;
        long time =0;

        PriorityQueue<Tester> q = new PriorityQueue<Tester>(//오름차순 정렬.
                (o1,o2)-> (int)((o1.spendT+o1.startT) - (o2.spendT+o2.startT))
        );

        for(long t : times)
            q.offer(new Tester(0, t));//0초일때 모두 넣는다.

        for(long i =0; i<n; i++){
            Tester completedTester = q.poll();
            time = completedTester.spendT + completedTester.startT;
            //System.out.println(time);
            q.offer(new Tester(time , completedTester.spendT));//새로운 Tester 추가
        }

        return time;
    }
}

성공코드(이분탐색)

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public static long solution(int n, int[] times) {
        long answer = 0;
        //오름차순 정렬
        Arrays.sort(times);

        //이분탐색을 위한 초기 범위 설정
        //처음에는 비어있는 심사관 수만큼은 바로 심사했다고 생각하고 최대 걸리는 시간
        int baseNum = Math.max((n - times.length), 1);
        long front = 1;
        long rear = (long) times[times.length-1] * baseNum;
        answer = rear;

        while (front <= rear){
            //기준 시간
            long mid = (front + rear) / 2;
            System.out.println(mid);
            //기준 시간보다 작다면 해당 심사 시간으로 가능한 심사개수 카운팅
            long count = countTime(mid, times);
        
            if(count < n) front = mid+1;
            else {
                answer = Math.min(answer, mid);
                rear = mid-1;
            }
        }
        return answer;
    }

    private static long countTime(long mid, int[] times) {
        long count = 0;
        for(int i=0; i<times.length; ++i){
            count += (mid / times[i]);
        }
        return count;
    }

}

 

 

징검다리

import java.util.Arrays;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks);
        int left = 0;
        int right = distance;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            int prv = 0;
            int removeCnt = 0;
            for (int i = 0; i < rocks.length; i++) {
                if (rocks[i] - prv < mid) {
                    removeCnt++;
                    if (removeCnt > n) {
                        break;
                    }
                } else {
                    prv = rocks[i];
                }
            }
            if (removeCnt > n) {
                right = mid - 1;
            } else {
                answer = answer > mid ? answer : mid;
                left = mid + 1;
            }
        }
        return answer;

    }
}

in-intuition.tistory.com/21

[프로그래머스] 징검다리(Java) [이분탐색]