[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) [이분탐색]