728x90
반응형
자료구조와 알고리즘 정리내용
이분 탐색(binary search)의 기본적인 알고리즘 과정
1. 주어진 배열을 순서대로 정렬
2. 배열의 최소 길이(=하위 인덱스, start)와 최대 길이(=상위 인덱스, end)를 기준으로 중간값(mid)값을 구함
3. 추측값(guess)과 원하는 값(item)을 비교하여 start 또는 end 값을 바꾸어 범위를 좁혀나가며 원하는 값을 찾음.
[프로그래머스]
이분 탐색 - 입국 심사
import java.util.Arrays;
class Solution {
public long solution(int n, int[] times) {
long answer = 0;
Arrays.sort(times); // 이분탐색 조건: 정렬
long start, end, mid; // 시간의 최소값, 최대값, 중간값 초기화
start = 0;
end = (long)times[times.length-1] * n; // 시간의 최대값
answer = end;
while(start <= end){
long sum = 0; // 입국심사 시간의 총합
mid = (start+end)/2;
for(int time : times){ // 주어진 시간에서 빨리 심사하는 심사관 순으로 심사처리
sum += mid/time; //입국자 수 = 추정시간 값/심사관 당 심사시간
}
if(sum < n){ // 해야할 인원보다 적게 처리를 적게함 -> 시간이 더 필요함
start = mid+1; // 시간의 최소값을 높임
} else{ // 해야할 인원보다 더 많이 처리함 -> 시간을 줄여 최적의 시간을 찾아냄
answer = mid;
end = mid-1; // 시간의 최대값을 낮춤
}
}
return answer;
}
}
이분 탐색의 기본 알고리즘은 주어진 배열에서 시작(start)과 끝(end)를 지정할 수 있었다면,
이 문제에서는 모든 사람의 입국 심사하는데 걸리는 총 소요시간을 주어진 배열이라고 생각하고 시작(0분)과 끝(max분)을 지정하여 풀어야 한다.
입출력 예
n | times |
6 | [7, 10] |
times의 배열(주어진 배열)은 0분 ~ 60분 이 된다.
60분 = 모든 대기자가 입국 심사가 10분이 걸리는 2번 심사관에게 갔을 때
*주어진 배열을 선택할 줄 알아야 풀 수 있는 문제였다.
반응형
728x90
'코딩 테스트' 카테고리의 다른 글
[자료구조와 알고리즘: JAVA 백준] 코딩테스트 연습 - 에디터 (0) | 2022.03.12 |
---|---|
[자료구조와 알고리즘: JAVA 백준] 코딩테스트 연습 - 선택 정렬5 (0) | 2022.03.11 |
[자료구조와 알고리즘: JAVA 백준] 코딩테스트 연습 - 선택 정렬1 (0) | 2022.03.11 |