코딩테스트 with JS/자바스크립트 알고리즘 문제풀이(인프런)
마구간 정하기(결정 알고리즘), 이분검색
5_hyun
2022. 12. 15. 20:11
반응형
코드
function solution(c, stable) {
let answer;
stable.sort((a, b) => a - b);
let lt = 1,
rt = stable.slice(-1)[0];
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
let ep = stable[0];
let count = 1;
for (let i = 1; i < stable.length; i++) {
if (stable[i] >= ep + mid) {
count++;
ep = stable[i];
}
}
if (count >= c) {
answer = mid;
lt = mid + 1;
} else rt = mid - 1;
}
return answer;
}
풀이 방법
이 문제도 이분검색으로 풀어야하는 문제이다.
-lt, rt의 정의
두 말 사이의 거리는 [1, 가장 큰 마구간의 좌표]이다. 배열에서 가장 작은 값이 100이어도 다음 숫자는 101부터 올 수 있기 때문에 두 말 사이의 최소값은 1이다. 따라서 lt에 1, rt에 가장 큰 마구간의 좌표를 넣는다.
-while문
1. while문의 종료 조건은 lt <= rt로 두고 mid도 (lt + rt) / 2로 둔다.(이분 검색의 초반과 같음)
2. count는 현재 둔 말의 수이며 처음에 1로 둔다. 왜냐하면 가장 첫번째 마구간에는 무조건 말을 넣어야 하기 때문이다.
3. 여기서 mid는 두 말 사이의 최대 거리이다. 따라서 ep에는 가장 첫번째 마구간 좌표를 넣는다. 그러면 ep + mid보다 크거나 같은 마구간 좌표에 다음 말을 둘 수 있다.
4. for문은 가장 첫번째 마구간에는 무조건 말이 들어가니 1부터 시작한다. for문 안에서 현재 마구간이 ep보다 크거나 같은 좌표에 있다면 count를 1 올려주고 ep도 현재 좌표로 최신화한다.
5. for문이 끝나고 나서 count >= c이면 answer에 mid를 저장한다. 그리고 mid를 더 늘려야하기 때문에 lt = mid + 1을 한다.
count < c이면 mid를 줄여야하기 때문에 rt = mid - 1을 한다.
반응형