2019 카카오 개발자 겨울 인턴십 코테(징검다리 건너기)

https://programmers.co.kr/learn/courses/30/lessons/64062

첫번째 시도

function solution(stones, k) {
    let answer = [];
    let start = 1;
    stones.map((stone,i)=>{
        if(i<=stones.length-k){
            let count = [];
            for(let j = i; j<k+i;j++){
                count.push(stones[j]);
            }
        answer.push(Math.max(...count));
        }
    })
    return Math.min(...answer);
}

분석

처음 문제를 볼 때만해도 오? 너무 쉬운데? 했지만... 바로 효율성 빵점이 나왔다... 효율성에서 빵점이 나왔다는 것은 알고리즘을 잘못 사용했을 가능성이 높다고 생각한다.
[제한사항]

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

제한사항을 보면 배열의 크기와 원소들이 값이 엄청 크다. 효율성을 높여줄 수 있는 알고리즘을 더 추가해줘야겠다. 공부가 더 필요할 것 같은데 알고리즘의 효율성을 높여주려면 어떤 스킬이 필요할까?

필요 스킬

• 이분탐색... (어떻게 구현? 왜 필요한가...).

두번째 시도

이분탐색을 해야하는 것 까지는 알겠다. 하지만 어떻게 사용해야 할 지는 도무지 아이디어가 떠오르지 않았다. 도대체 뭘 반으로 쪼개야하니... 자존심이 많이 상했지만...ㅠ 검색을 통해서 약간이 아니라 많은 힌트를 얻었다.

• 2억을 이분해야한다.

function solution(stones, k) {
    return BS(stones,k, 1, 200000000);
}

const BS= (stones,k,min,max)=>{
    if(min===max){
        return min;
    }
    let mid = Math.floor((max+min)/2);
    let count = 0;

    for(let i=0; i<stones.length;i++){
        if(count ===k){
            break;
        }
        let value = stones[i] -mid;
        value > 0 ? count=0 : count ++ ;
    }
    if(count ===k){
       return BS(stones, k, min,mid);
    }else{
       return BS(stones, k, mid+1, max);
    }
}

답을 보았지만 최대한 논리를 이해하고 안보고 코드를 짜도록 노력했다. 며칠 뒤에 다시 한번 풀어보고 완전히 나의 것으로 만들자.