카카오 인턴쉽 2019 코딩테스트 - 징검다리 건너기

5월 3일에 푼 문제입니다🌷
징검다리 건너기
정확도와 효율성을 채점하는 문제이다.

통과한 코드

function solution(stones, k) {
    return bs(stones,k,0,200000000)
}

const bs=(stones,k,min,max)=>{
    if(min===max){ return min}
    let mid = Math.round((min+max)/2)
    let result=0
    
    for(let i=0;i<stones.length;i++){
        if(result===k){
            break
        }
        let stone=stones[i]-(mid-1)
        stone<=0?result++:result=0
    }
    if(result===k) {return bs(stones,k,min,mid-1)}
    else {return bs(stones,k,mid,max)}
    
}

binary Search를 이용해서 푼 문제이다.
문제에서 주어진 stones의 최소인 0과 최대인 200000000로 입력한다.

최소값과 최대값의 중간값인 mid명이 징검다리를 통과할 수 있다면 min~mid 명은 당연하게 징검다리를 건널 수 있다. 따라서 min~mid 명을 구하지 않아도 된다!!

mid 명이 다리를 건넜을 때 연속된 밟을 수 없는 stones 개수가 k개이면
mid명이 징검다리를 건널 수 없으므로
max를 mid-1로 설정하고 min~mid-1 범위로 재귀적으로 계산한다.

mid 명이 다리를 건넜을 때 연속된 밟을 수 없는 stones의 개수가 k개 이하이면 mid 명이 징검다리를 건널 수 있다.
min을 mid로 입력하고 mid~max 범위로 재귀적으로 계산한다!

이분법으로 풀었더니 테스트를 통과할 수 있었다!

삽질의 흔적,,

function jumpstone(jump,stones,i){
    const value=jump.get(i)
    if(stones[value]!=0){
        return value
    }
    let p=jumpstone(jump,stones,value)
    return p
}
function solution(stones, k) {
    var answer = 0;
    var jump = new Map();
    stones.unshift(Infinity);
    var length=stones.length
    for(let i=0;i<length;i++){
        jump.set(i,i+1)
    }
    while(1){
        var stop=false
        for(let [key,value] of jump){
            stones[key]-=1
            value = jumpstone(jump,stones,key)
            if(value-key>k){
                stop=true
                answer-=1
                break
            }
            jump.set(key,value)
        }
        answer+=1
        if(stop) break
    }
    return answer;
}

map을 이용해서 key의 stones가 0이면 value를 전의 key에 입력해주었다.
즉 0인 stone은 map에서 제거해서 반복문을 적게 돌려고 했다.
하지만 정확도는 모두 맞았으나 효율성에서 0점,,,,ㅠㅠㅠㅠ