[프로그래머스] 2019카카오 겨울 인턴십 - 징검다리 건너기

오늘 푼 문제

 

4. 징검다리 건너기 / Lv.3 / 시간 : 124분(시간초과)

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

코딩테스트 연습 - 징검다리 건너기

 

1차 시도 - 효율성 테케 13 시간초과

function solution(stones, k) {    
    let max = Math.max(...stones.slice(0,k));
    var answer = max;
    for(let i=0; i<stones.length-k;i++){
        let j = i+k;
        let [de,ne] = [stones[i], stones[j]];
        if(de===max) max = Math.max(...stones.slice(i+1,j+1))
        if(max<answer) answer = max;
    }

    return answer;
}

 

로직은 괜찮았다고 생각했으나.. max를 새로 업뎃해야 하는 부분에서 아무래도 문제가 있었다...

전반적인 효율성도 준수한 편인데 13같이 괴랄한 경우는 아예 out of control 되는 게 문제임;

 

 

2차 시도 - 이진 탐색을 이용해 max값을 업데이트 해가면서 찾음

function solution(stones, k) {    
    let answer;
    let list = [...new Set(stones)].sort((a,b)=>a-b);
    let [s,l] = [0,list.length-1]; 
    while(true){
        let config = -1;
        let cnt = 0;
        let over = 0;
        let mid = Math.ceil((s+l)/2);
        let max = list[mid];
        for(let i=0;i<stones.length;i++){
            let cur = stones[i];
            if(cur<max){
                over++;
                cnt++;
            }else if(cur===max) {
                over = 0;
                cnt++;
            }
            else{
                over = 0;
                cnt = 0;
            }
            if(cnt===k) config = 0;
            if(over>=k){
                config = 1;
                break;
            }
        }
        switch(config){
            case -1: // max 크게
                s = mid+1;
                if(s>l) return max;
                break;
            case 0: //max 그대로
                return max;
                break;
            case 1: //max 작게
                l = mid-1;
                if(s>l) return max;
                break;
        }
        
    }
    return answer;
}

 

이진탐색 적용하려니 존나 헷갈림.

통과는 했지만 전반적인 효율성은 떨어진다. 코드도 별로 마음에 들지 않음... 더 좋은 방법을 고려해보겠음

 

 

 

!! 카카오 기술 블로그 공식 해설에서 충격적인 글을 발견

 

https://tech.kakao.com/2020/04/01/2019-internship-test/

O(n)으로??? 탐색??? 가능??? ㄹㅇ??????????????

내가 기필코 풀고 만다