프로그래머스 Level 4 - 징검다리
📌 문제 설명
📌 생각한 풀이 방법
- 초기에 최소값과 최대값 distance의 mid를 기준값으로 설정한다.
- mid를 기준으로 이전값 previous와의 차이를 구한다.
2-1. 해당 차이가 mid보다 작다면 removeCount를 증가시킨다.
2-2. 해당 차이가 mid보다 크다면 현재 바위를 previous값으로 바꾼다.
3-1. 제거된 바위 갯수가 n보다 크면 max를 mid-1로 바꾼다.
3-2. 제거된 바위 갯수가 n보다 크면 min를 mid+1로 바꾼 후, answer과 비교를 하여 answer보다 값이 크다면 해당 값으로 바꾼다.
- min과 max가 만나기 전까지 2~3과정을 반복한다.
📌 풀이
function solution(distance, rocks, n) {
let answer = 0;
let min = 1;
let max = distance;
rocks.sort((a, b) => a - b);
while (min <= max) {
let removeCount = 0;
let previous = 0;
let mid = Math.floor((max + min) / 2);
for (let i = 0; i < rocks.length; i++) {
if (rocks[i] - previous <= mid) {
removeCount++;
} else {
previous = rocks[i];
}
}
if (removeCount > n) {
max = mid - 1;
} else {
min = mid + 1;
answer = Math.max(answer, min);
}
}
return answer;
}