프로그래머스 > 완전탐색 > 카펫
https://programmers.co.kr/learn/courses/30/lessons/43238?language=java
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
n | times | return |
---|---|---|
6 | [7,10] | 28 |
처음에 어떻게 이분탐색을 시작해야될지 감을 1도 못잡았다.
근데 보다보니, times
배열의 최고 값을 기준으로 이분탐색하면서 mid
값으로 각 심사관이 몇명을 검색할 수 있냐만 계산하면
최소값을 구할 수 있었다.
max
는 times
가 오름차순으로 정렬 됬을 때,
times[times.length-1]
(가장 뒤) 에서 n
명 만큼 곱하면된다.
이게 최악의 경우의 수인 max
값이 된다.
이제 mid
를 구하기 위해 min
과 max
를 비교하면서 반복한다.
min
이 max
를 넘어가는 순간 while문은 종료된다.
max
와 min
의 범위를 게속줄여가면서 mid
값을 수정하고
해당 mid
값으로 times
배열의 시간 값을 가진 심사관들이 몇명을 심사할 수 있는지 sum
으로 합한다
여기서 sum
이 n
보다는 당연히 크거나 같아야 한다.
작으면 시간안에 검색을 못한다는거니까 볼 것도 없다.
만약 크거나 같을경우, answer
을 mid
값으로 갱신을 시켜주며
우리는 마지막에 최소값을 반환할 수 있게 된다.
입국심사 오래걸려도 그냥 좀 한줄로 서지;;
import java.util.*; class Solution { public long solution(int n, int[] times) { Arrays.sort(times); long min = 1; // times 배열의 최악의 경우는 범위 // n명 기준으로 times의 가장 마지막 시간까지 탐색하는 경우. long max = (long) times[times.length-1]*n; long mid = 0; long sum; long answer = max; while(min <= max) { sum = 0; mid = (min + max) / 2; for(int time : times) { sum += mid / time; } if(sum >= n) { answer = mid; max = mid - 1; } else { min = mid + 1; } } return answer; } }