문제 출처
https://school.programmers.co.kr/learn/courses/30/lessons/43238(프로그래머스)
학습 키워드
이분탐색
시도 방법
가장 오래걸리는 시간부터 이분탐색을 통해 범위를 줄여나가면서
가장 적합한 시간대를 찾았다.
내가 작성한 코드
import java.util.Arrays;
class Solution {
public long solution(int n, int[] times) {
Arrays.sort(times);
long maxTime = times[times.length-1];
long start = 0 ;
long end = maxTime * n ;
long mid = 0;
long answer = 0 ;
//이분 탐색
while(start <= end) {
long people = 0 ;
mid = ( start + end ) / 2 ;
for(int time : times) {
people += mid / time;
if(people >= n) break;
}
if(people >= n) {
answer = mid;
end = mid - 1 ;
} else if(people < n) {
start = mid + 1 ;
}
}
return answer;
}
}코드설명
times = [1,2,3,4,5] , 심사받을 인원 : 10명일때 예를 들어보겠다.
먼저 times 중에 가장 오래걸리는 시간을 찾았다.
위의 경우 5 times 가 가장 오래 걸리는 시간이고 만약 모든 인원이 이 곳에서 심사를 받는다면 최대 50 초가 걸리게 된다. 따라서 start = 0 ~ end = 50 사이에 데이터를 반복 탐색하면서 최적화된 값을 찾는다.
while start = 0 , end = 50 , mid = 25
25초를 기준으로 인원을 확인해보겠다.
먼저 25 / 1 = 25명을 처리할 수 있다.요구하는 10명을 이미 뛰어넘었으므로 break을 하고 아래 answer 에 해당 25라는 값을 넣고 end 를 mid-1 로 줄임으로써 이분 탐색을 한다.
while start = 0 , end = 24 , mid = 12
12초를 기준으로 인원을 확인해보자.
먼저 12/ 1 = 12명을 처리할 수 있다.요구하는 10명을 넘었고, 25분보다 12분이 더 빠르므로 값을 변경한다. (answer = 12, end = 5)
while start = 0 , end = 5 , mid = 2
2초를 기준으로 인원을 확인해보자.
2 / 1 = 2명을 처리할 수 있다. 2/2 = 1명을 처리할 수 있다.
그 다음부터는 모두 0이 더해지고 else if 로 빠지므로 start = 3 으로 처리된다.
whie start = 3 , end = 5 , mid = 4
4초를 기준으로 인원을 확인해보자
4/1 = 4명 처리 , 4/2 = 2명 처리 , 4/3 = 1명 처리 , 4/4 = 1명 처리
총 8명처리된다. 아직 10명 보다는 부족하므로 start = 4+1로 하고 넘어간다
while start = 5 , end = 5 , mid = 5
5/1 = 5명 처리 , 5/2 = 2명처리 , 5/3 = 1명 처리 , 5/4 = 1명 처리 , 5/5 = 1명처리 이 경우 10명이 처리되기 때문에 answer = 5 가 들어가게되고
비교문은 종료된다.
출력결과
새롭게 알게된 점
주의할 점으로 int 는 최대 약 21억4천의 값만 받을 수 있다.
따라서 이를 넘어서는 값을 숫자로 받으려면 long을 활용해야 한다.
다음에 풀어볼 문제 - ??
#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL
