Portfolio

징검다리 건너기

📄문제

✏️풀이

재영


/*
  1. 이분탐색을 위한 함수
  2. 체크할 때 true, false를 내뱉는 함수
*/

const isAllCrossed = (stones, k, mid) => {
  let cnt = 0;
  const stonesLength = stones.length;
  for (let i = 0; i < stonesLength; i += 1) {
    cnt = (stones[i] <= mid) ? cnt + 1 : 0;
    if (cnt >=  k) return false;
  }
  return true;
}

const binarySearch = (arr, k, isPossibleCallback) => {
  let start = 1;
  let end = 200000000;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (isPossibleCallback(arr, k, mid)) start = mid + 1
    else end = mid - 1
  }
  return start;
}

const solution = (stones, k) => {
  return binarySearch(stones, k, isAllCrossed);
}

효성


function canCross(stones, k, crossCnt) {
    let jumpChance = k;
    for(let pos = 0; pos < stones.length; pos++) {
        if(stones[pos] >= crossCnt) {
            jumpChance = k;
            continue;
        }
        jumpChance--;
        if(jumpChance === 0) {
            return false;
        }
    }
    return true;
}


function getMaxCrossCnt(stones, k, left, right) {
    let maxCrossCnt = 1;
    while(left <= right) {
        const mid = (left + right) >> 1; 
        if(canCross(stones, k, mid)) { 
            maxCrossCnt = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return maxCrossCnt;
}

function solution(stones, k) {
    const maxCnt = stones.reduce((acc, cur) => Math.max(acc, cur));
    const minCnt = 1;
    return getMaxCrossCnt(stones, k, minCnt, maxCnt);
}

💡

1. 이진 탐색 → 가정한다는 사실이 중요함!!! mid는 가정임. 2. 스프레드 연산자는 시간 초과됨.

은찬


const binarySearch = (stones, mid, k) => {
    let count = 0;
    
    for(let i = 0; i < stones.length; i++){
        if(stones[i] - mid <= 0){
            count++;
        } else{
            count = 0;
        }
        
        if(count >= k){
            return true;
        }
    }
    
    return false;
}

const solution = (stones, k) => {
    let front = 0;
    let back = 200000000;
    
    while(front <= back){
        const mid = Math.floor((front + back) / 2);
        
        if(binarySearch(stones, mid, k)){
            back = mid - 1;
        } else{
            front = mid + 1;
        }
    }
    
    return front;
}

희진

일부만 통과


function solution(stones, k) {
	let count = 0;
	let factor = true;
	const maxVoid = "0".repeat(k);
	const minStone = Math.min(...stones);
	stones =  stones.map(a => a-minStone);
	count += minStone;
		while(factor){
			let findStone = stones.join('');
				if(findStone.includes(maxVoid)){
					factor = false;
					break;
					}
			stones = stones.map(a=> a>0 ? a-1 : 0);
			count++;
		}
return count;
}