[프로그래머스]징검다리 건너기 (JS)
6280 단어 programmersprogrammers
문제
[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기
[링크]https://programmers.co.kr/learn/courses/30/lessons/64062
문제풀이
처음 문제를 보고서 배열크기(2십만)
,배열원소(2억)
에 겁을 먹고 시간복잡도 N
으로 풀 수 있는 공식(?)을 찾아보려 고민하였는데, 쉽지 않았다.
그런데 답의 최대값인 배열원소(2억)
의 로그2 값
이 계산해보니 27.57
밖에 안되더라.. 이분 탐색
으로 푸는 문제인 것을 대놓고 제한사항
에 적어준 것이었다.
이분탐색으로 정답을 정하고 그 값이 조건에 부합하는지 체크해주면 해결.
코드
function solution(stones, k) {
let max=0,min=Infinity,answer=1;
for(let i=0;i<stones.length;i++)max=Math.max(max,stones[i]),min=Math.min(min,stones[i]);
if(max===min)return max;
while(min<=max){
const mid = Math.floor((max+min)/2);
const temp = [...stones];
let count=0;
for(let i=0;i<temp.length;i++){
temp[i]-mid>=0?count=0:count++;
if(count>=k){
max=mid-1;
break;
}
}
if(count<k)answer=Math.max(answer,mid),min=mid+1;
}
return answer;
}
Author And Source
이 문제에 관하여([프로그래머스]징검다리 건너기 (JS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dowon938/프로그래머스징검다리-건너기-JS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)