카카오 인턴쉽 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점,,,,ㅠㅠㅠㅠ
Author And Source
이 문제에 관하여(카카오 인턴쉽 2019 코딩테스트 - 징검다리 건너기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mlsh1112/카카오-인턴쉽-2019-코딩테스트-징검다리-건너기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)