[해커랭크] Minimum Time Required (Search)

 

문제 요약 : 기계마다 제품 한개를 만드는데 걸리는 시간이 다르다.
제품 한 개를 만드는데 걸리는 시간이 주어졌을 때 목표 생산량을 채우려면 최소 몇일이 소요 되는가?

INPUT
기계 대수 / 목표생산량
각 기계별 제품 1개 생산소요 시간

접근법)
이 문제는 몇일이 걸릴지 시간을 찾는(SEARCH) 문제이다. 탐색을 위해서는 우선 탐색하고자 하는 값의 범위에 대한 정의가 필요하다.
최소시간 ~ 최대 시간 중 binary 탐색을 통해 조건을 만족하는 시간을 찾을 것이다.
최소시간 : 모든 기계의 생산량이 하루 생산량이 가장 적은 기계와 같다고 가정.
                -> 필요한 시간 = 목표생산량 * max(생산 소요 시간) //기계대수
최대시간 : 모든 기계의 생산량이 하루 생산량이 가장 많은 기계와 같다고 가정.
                -> 필요한 시간 = 목표생산량 * min(생산 소요 시간) //기계대수

 

총(예상) 시간을 각 기계별 소요시간으로 나누면 생산량이 나온다.

처음에 아래와 같이 로직을 짜니 값이 맞지 않는 case가 많았다.

디버깅을 해보니, 아래와 같은 로직에서는 필요한 최소시간이 도출되지 않는다.
cnt==goal 을 만족하는 time은 여러개가 있을 수 있고 우리는 그중 최소 time이 필요하다.

그래서 cnt가 goal 보다 클때 or 같을때 계속해서 범위를 time을 줄여나가야 한다.
그래서 cnt>=goal 일때로 조건을 변경해야한다.

* 계속해서 end를 줄여나간 것이기 때문에 end가 start보다 더 작아지면 start를 반환해야함.
binary search이므로 O(nlogn)