프로그래머스 LV-4 무지의 먹방 라이브

이 문제를 사실 좋은 방법으로 풀었다고는 생각이 안들어요... 근데 제 기준으로 신박하게 해결했다고 생각해서 남겨보려해요..ㅎㅎ

 

일단 문제는 간단하게 food_times라는 음식을 섭취할 수 있는 개수에 대한 리스트가 있어요.

그리고 k번 섭취한 후에 다음으로 섭취할 음식의 인덱스를 구하는 문제에요.

 

일단 food_times의 길이가 200,000 이고 원소는 100,000,000 이기 때문에 k섭취를 위해 이중 for문을 돌리게 되면 최악으로 100,000,000 * 200,000 회? 되는거죠??

네, 아마 그정도쯤 될거라 생각이 들어 당연히 호율성에서 안돼요!

 

N을 100,000,000으로 M을 200,000 으로 생각해보면 O(MN)보단 작아야지 효율성에 통과될거에요.

 

그래서 첫번째 목표는 이분탐색을 통해 food_times의 원소를 이분탐색으로 자르며 섭취한 총 양을 k와 비교하여 찾는거에요!

여기서 O(logN) 으로 아~주 작아요!

 

function solution(food_times, k) {
    let right = 100_000_000;
    let left = 0;

    while(left <= right){
        const mid = Math.floor((left + right) / 2);
        const sum = food_times.reduce((acc,curr) => {
            if(curr <= mid) acc += curr
            else acc += mid
            return acc
        }, 0)
        if(sum < k) left = mid + 1
        else right = mid - 1
    }
}

 

** 대표적인 이분탐색 로직이니 꼭!! 방법을 외워야지 나중에 다른 문제에서도 적용할 수 있어요 ㅎ

 

그렇게 k번 먹게된 left를 얻었고, 이제부터 다음 섭취할 인덱스를 어떤식으로 구할까 고민을 했죠...

무턱대고 left 값을 food_times의 모든 값에서 뺀다면 몇번째 인덱스까지 먹었는지 알 수 없다고 생각해서 left - 1번까지 먹게 했어요. 여기서 O(M) 계산이 나와요.

 

    const prevVal = left - 1
    food_times = food_times.map(a => {
        if(a <= prevVal) {
            k -= a
            return 0
        } else {
            k -= (prevVal);
            return a - (prevVal)
        }
    })

 

 

그리고 남은 k만큼 (여기서 k는 빼고 남은 수 이므로 최대 20만(M)) 추가로 food_times에서 값을 빼주다가 k가 0이 되는 시점에 남아있는 food_times의 원소중 가장 빠르게 만나는 인덱스를 찾아주면 해결이 돼요!

여기서도 최대 O(M)이니 총 O(logN + 2M)으로 효율성에도 통과하는걸 확인할 수 있었어요!

 

while(k > 0){
        for (let i = 0; i < food_times.length; i++){
            if(food_times[i]){
                food_times[i] -= 1;
                k -= 1;
            }
            if(k === 0) {
                for(let j = i + 1; j < food_times.length; j++){
                    if(food_times[j]) return j + 1;
                }
                return food_times.findIndex(a => a) + 1
            }
        }
    }

 

** 최종코드

 

개인적으로 food_times를 크기순으로 정렬 후, 빼는것보다 이분탐색을 사용하고 싶고 더 빠르다고 생각했다!

 

function solution(food_times, k) {
    const maxSum = food_times.reduce((acc,curr) => acc + curr, 0);
    if(k >= maxSum) return -1;

    let right = 100_000_000;
    let left = 0;

    while(left <= right){
        const mid = Math.floor((left + right) / 2);
        const sum = food_times.reduce((acc,curr) => {
            if(curr <= mid) acc += curr
            else acc += mid
            return acc
        }, 0)
        if(sum < k) left = mid + 1
        else right = mid - 1
    }
    const prevVal = left - 1
    food_times = food_times.map(a => {
        if(a <= prevVal) {
            k -= a
            return 0
        } else {
            k -= (prevVal);
            return a - (prevVal)
        }
    })
    while(k > 0){
        for (let i = 0; i < food_times.length; i++){
            if(food_times[i]){
                food_times[i] -= 1;
                k -= 1;
            }
            if(k === 0) {
                for(let j = i + 1; j < food_times.length; j++){
                    if(food_times[j]) return j + 1;
                }
                return food_times.findIndex(a => a) + 1
            }
        }
    }
}