function solution(stones, k) {
let left = 1;
let right = stones.reduce((acc, item) => item > acc ? item : acc, stones[0])
while (left <= right) {
const mid = Math.floor((left + right) / 2);
let continuousZero = 0;
let possible = true;
for (let i = 0; i < stones.length; i++) {
if (stones[i] < mid) {
continuousZero++;
if (continuousZero >= k) {
possible = false;
break;
}
} else {
continuousZero = 0;
}
}
if (possible) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left - 1;
}문제 해석
정답 알고리즘 - 이분탐색
처음에는 여러가지 방법이 떠올랐습니다.
첫 번째는 stones배열을 0번째 인덱스부터 k+2길이만큼 슬라이싱해서 젤 앞과 젤 뒤가 가운데 k개들 보다 큰지를 비교하는 것입니다. 그렇게 해서 가운데 k개들 보다 크다면 그 구간을 지나갈 수 없는 것이고 양 끝 값 중 작은 값 - 1을 하면 답이 됩니다.
하지만 슬라이싱이라는 것 때문에 효율성이 좋지 않을 것 같아 바로 포기하였습니다.
두 번째는 stones의 최댓값부터 1씩 줄여나가며 간격이 k보다 작거나 같은 값을 찾는 것이였습니다.
예를 들어 4라는 값으로 탐색하고 있다면 문제의 테스트케이스에서는 가장 멀리 떨어진부분의 길이가 4입니다. 이는 k = 3일때 건너지 못한다는 뜻입니다.
이보다 1줄여 3이라는 값으로 탐색하고 있다면 가장 멀리 떨어진부분의 길이가 2입니다. 이는 k = 3일때 건널 수 있다는 뜻입니다.
즉, 3일때는 건너고 4일때는 건너지 못하니 최대 3명 건널 수 있습니다.
하지만 이 방법도 시간초과에 걸리게 되었습니다.
결국 마지막으로 생각해 낸 방법이 이분탐색이였습니다.
어떤 범위내에서 하나의 값을 탐색할 때 자주 사용되는 방법인데 생각해내는 데에 너무 오랜시간이 걸렸습니다...ㅠㅠ
초기값의 left를 1, right를 stones의 최댓값으로 설정해 놓고 시작하게 됩니다.
풀이 방향
1. left = 1, right = max(stones)로 설정해놓고 시작합니다.
2. 연속해서 몇 개의 돌다리를 건넜는지 체크하는 'continuousZero', 가능한 지를 판단하는 'possible' 변수를 설정해줍니다.
stones배열을 앞에서부터 탐색하며 mid보다 값이 작다면 건널 수 있는 것이므로 continuousZero 변수를 1 늘려줍니다. 진행 중 stones의 값이 mid보다 크거나 같다면 continuousZero 변수를 0으로 만들어줍니다.
진행 중 continuousZero 변수의 값이 k보다 커지게 된다면 돌다리를 건널 수 없게 된 것이므로 possible 변수를 false로 바꿔주고 반복문을 종료합니다.
3. possible 변수가 false이면 건널 수 없는 것이므로 left++, possible 변수가 true이면 건널 수 있는 것이므로 right-- 해줍니다.
4. left <= right인 상황이 오면 이분 탐색을 종료해줍니다.
주의할 점
배열의 최댓값을 구할 때
Math.max(...stones)(배열의 모든 요소를 메모리에 올려놓음)
가 아닌
stones.reduce((acc, item) => item > acc ? item : acc, stones[0])(acc값만 메모리에 올려놓음)
로 구해야합니다.
첫 번째 방법으로 최댓값을 구할 시 메모리를 과도하게 사용하게 되어 효율성 검사 케이스에서 런타임 에러가 생기게됩니다.
배열의 크기가 매우 큰 경우에는 .reduce를 이용하여 최댓값을 구해야 한다는 것을 기억합시다!!
