과일장수

문제

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.
한 상자에 사과를 m개씩 담아 포장합니다.
상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.
과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)

예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.

(최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8
사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

입출력 예

첫시도 & 시나리오

1. 먼저 score를 내림차순으로 정렬

2. 반복문을 돌리면서 상자에 담을 수 있는 m만큼만 splice메서드로 잘라낸다

3. splice로 잘라낸뒤 temp배열에 담는다.

4. answer에 temp배열에 있는 요소들을 계산한다.

문제점

테스트는 패스했지만 제출하면 시간초과걸림

문제점 파악

질문을 보니 score의 길이가 100만이 넘는 경우가 있어 splice메서드가 시간초과의 원인임을 파악
splice메서드를 안쓰는 방향으로 생각함

최종코드

function solution(k, m, score) {
    var answer = 0;
    // 내림차순으로 정렬하고 appleArr에 깊은 복사
    let appleArr = score.slice().sort((a, b) => b - a)
    for(let idx1 = 0; idx1 < score.length; idx1++) {      
    	// 남은 요소의 수가 m보다 적을 때 반복문 중단
        if(appleArr.length - idx1 < m) {
            break;
        }
        let temp = []
        let temp2 = idx1
        // temp에 담을 때 현재의 idx1에서 m만큼의 요소를 담는다.
        for(let idx2 = idx1; idx2 < (temp2 + m); idx2++) {
            temp.push(appleArr[idx2]);
        }
        // temp에 다 담아 질때마다 answer에 박스값을 계산한다.
        answer += (Math.min.apply(null, [...temp]) * m)       
        // 얘가 문제였네
        idx1 += m - 1
    }
    return answer;
}