[JS] 무지의 먹방 라이브

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/42891

프로그래머스

 

 

 

시간 효율성을 생각하기 위해서 따져야 할게 조금 있는 문제였다.

 

최솟값을 전체 배열에서 빼준다면 아래와 같이 효율적으로 진행을 하는 것이 가능하다.

[3,1,2] -> [2,0,1] -> [1,0,0] 

이를 반복해 주면서 k > (현재 배열의 최솟값) * (현재 배열의 길이) 를 충족하면 계속 반복해주면 된다.

 

 

 

1. 먼저 정답이 -1인 경우는 전체의 합이 k보다 작은 경우다. 

2. 이후 밥먹는 순서를 효율적으로 빼기 위해서 밥의 순서대로 정렬을 해준다. 후에 정답을 알아내기 위해서 음식번호를 가지고 있어야 한다. pop을 효율적으로 사용하기 위해서 내림차순으로 정렬을 해준다. (pop을 쓰면 가장 작은 수가 뽑히도록)

 

[3,1,2] -> [[3,1],[1,2],[2,3]] -> [[3,1],[2,3],[1,2]]

 

3. 맨 끝음식을 하나씩 뺀다는건 결국 계속해서 전체의 배열에 더해줘야하는데 두 간격의 차를 애초에 저장해두면 이를 반복할 필요가 없다.

 

[[3,1],[2,3],[1,2]] -> [[1,1],[1,3],[1,2]] (차를 저장)

 

4. food_times에서 pop을 해주며 k를 쭉 빼준다. 이때 해당 배열에 0이 들어간 부분들은 모두 제거를 해줘야 최솟값이 같은 경우를 생각할 수 있다.

 

5. k가 나왔다면 해당 k는 남은 food_times를 돌며 순서를 계산 할 수 있다. 따라서 나머지 연산자를 활용해서 몇번째 접시인지를 구해준다.

 

6. 배열을 다시 음식크기순으로 정렬한 후 k번째 접시를 구하면 정답이다.

 

 

 

 

 

function solution(food_times, k) {
    const total = food_times.reduce((a,c) => a+c , 0)
    if(total<=k) return -1
    
    food_times = food_times.map((v,i) => [v,i+1])
    food_times.sort((a,b) => b[0]-a[0])
    
    for(let i = 0 ; i < food_times.length-1 ; i++){
        food_times[i][0] -= food_times[i+1][0]
    }
    
    while(1){
        if(!food_times.length) break
        const min = food_times[food_times.length-1][0]
        if(k < min * food_times.length) break
        k -= min * food_times.length
        food_times.pop()
        while(food_times.length && !food_times[food_times.length-1][0]) food_times.pop()
    }
    
    k = k % food_times.length
    return food_times.sort((a,b) => a[1]-b[1]).filter((v,idx)=> idx===k)[0][1]
   
    
    
}