카카오 코딩테스트 모의고사 5번

5 min readApr 26, 2020

평소에 알고리즘 공부를 따로 하지 않으니 프로그래머스에서 시행하는 모의고사 및 테스트를 별일 없으면 신청해서 보는 편이다. 그러다 3.28일에 실시한 모의고사가 있어서 신청을 보았는데 마지막 문제가 이해는 쉬웠으나 효율성이 있어 해결이 어려웠다. 문제를 간단히 적어보면

카카오 초등학교의 니니즈 친구들이 라이언 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. 라이언 선생님은 니니즈 친구들이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다. 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다. 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다. 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다. 니니즈 친구들은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다. 니니즈 친구들은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다. 디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

처음에 접근하길 완전탐색으로 접근을 하였다. 모든 징검다리에서 숫자 하나씩 빼면서 0의 갯수를 계산하여 k보다 크고 작은 것을 판단하였다. 정확성 부분에서 70% 맞고 효율성에서는 0%를 얻었다. 아무래도 완전탐색을 하다보니 2억의 가까운 stones의 원소값에서 부하가 걸려 있었다.

첫번째 작성한 코드

function solution(stones, k) {
    let result = 0, finish=true;
    while(finish){
        for(let i=0; i<stones.length; i++){
            if(stones[i]){
                stones[i]-=1   
            }
        }
        if(stones.join("").includes("0".repeat(k))){
            finish = false
        }
        result++
    }
    return result
}

여러가지 시도(효율성을 증대시기키 위한 꼼수)를 해보았으나 접고 다른 방식으로 접근하기 시작했다. 그중 시도한 나와 인연이 깊은 이분 탐색이다. O(nlogm)의 효율성을 가지며 가능성을 절반씩 뚝뚝 깎아 내려가기에 위에 시도했던 방법으로는 최악의 경우의 수가 2억이라면 이분탐색으로는 절반의 경우의 수를 줄일 수 있다(최악일 뿐 훨씬 더 줄일 수 있는 구조가 많을듯).

mid, left, right를 설정하여 최대, 최소, 중간 값을 정하고 건널수 있는 0의 갯수를 계산하는 방식이다. 아래 코드를 통해 효율성 테스트 까지 성공하였다.

const checkFn = (mid, stones, k) => {
    let zeroCount = 0;
    for(let i=0; i<stones.length; i++){
        if(stones[i]-mid <=0){
            zeroCount++;
        }else{
            zeroCount = 0;
        }
        if(zeroCount>=k){
            return false;
        }
    }
    return true;
}function solution(stones, k) {
    // 이분탐색
    let left=1, right=200000000, count=0;
    while(left<=right){
        let mid = Math.floor((left + right)/2)
        if(checkFn(mid, stones, k)){
            left = mid+1;
        }else{
            right = mid-1;
        }
        count++
    }
    return left;
}

아래는 검색하여 찾은 코드인데 마찬가지로 이분탐색을 이용하여 해결하였다. 표현이 다를뿐 로직은 똑같은데 map을 이용해서 한 부분이 나의 for문 보다 좀 이뻐보인달까? 해서 적어보았다. 함수의 기능을 분류한 부분에서는 내 코드가 조금 더 나아 보인다. 기능을 나누니 파라미터도 줄어들어 좀 더 보기 좋은 것 같다.

const getMiddle = (min, max) => parseInt((min + max) / 2);const binarySearch = (min, max, arr, k) => {
    while (min <= max) {
        const middle = getMiddle(min, max);
        const result = arr.map(el => el - middle);
        let count = 0;
        for (const el of result) {
            if (el <= 0) {
                count++;
            } else {
                count = 0;
            }
            if (count >= k) break;
        }        if (count >= k) {
            max = middle - 1;
        } else {
            min = middle + 1;
        }
    }
    return min;
};const solution = (stones, k) => {
    // const max = Math.max(...stones);
    return binarySearch(0, 200000000, stones, k);
};

남의 코드도 잘 읽도록 하고 그리디, 탐색알고리즘, 동적 프로그래밍 등을 좀 더 공부하여 어느정도의 알고리즘 문제는 해결할 수 있는 실력을 기르도록 하자.

카카오 코딩테스트 모의고사 5번

Written by dongwon kim