[Programmers / JS] 135808번 - 과일장수

Problem

문제 보기

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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 함수를 완성해주세요.

---

Solution

문제분석
사과 1~k점 분류되어 있음
1상자에 m개씩 넣을 수 있다.
각 상자의 최저 점수 * 넣을 수 있는 사과수
상자채 팔았을 때 얻을 최대 이익 계산해야함
상자에 들어가지 못한 남은 사과는 버림
return (최저 점수 x 1상자에 넣을 수 있는 사과수 x 상자수) 모두 합한 값

문제풀이
1. 최대 이익을 계산해야하므로 각 상자의 최저 점수가 높은 점수가 될 수 있도록 해야한다
2. 우선 사과를 오름차순으로 정렬해준다.
3. 각 1상자에 넣을 수 있는 m만큼 score에서 빼낸 뒤 box에 push
4. 각각의 상자에서 가장 작은 수와 m을 곱한 뒤 모두 더해준다.

첫번째

function solution(k, m, score) {
    let box = [];
    score.sort((a, b) => b - a);

    while (m <= score.length){
        box.push(score.splice(0, m));
    }
    
    return box.map(x => Math.min(...x) * m).reduce((a, b) => a + b , 0);
}

위에 생각한 문제 풀이대로 코드를 작성하였다.
그런데...

테스트 1 ~ 24까지는 무난하게 통과했는데

테스트 11 ~ 15까지 시간 초과가 나왔다ㅜㅜ...
그래서 코드 보고... 단계를 뺄 수 있는 건 빼도록 코드를 다시 짜보았다

두번째

function solution(k, m, score) {
    let box = 0;
    score.sort((a, b) => b - a);

    while (m <= score.length){
    	let apple = score.splice(0, m);
        box += Math.min(...apple) * m;
    }
    
    return box;
}

우선 첫번째때 배열을 splice로 잘라내서 새 배열에 push해주는 과정이 메모리도 잡아먹고 시간상 오래 걸리는 거 같아서 수정해줬는데 이게 문제가 아니었다..똑같이 시간 초과가 났다^^....
배열을 잘라내서 저장하는 행위 자체가 뒤에서 빼내는 것이 아닌 앞에서 빼내는 거기 때문에 다시 정렬하는 등의 과정에서 시간이 오래걸리는 거 같다.

세번째

function solution(k, m, score) {
    let box = 0;
    let count = m-1;
    score.sort((a, b) => b - a); 
    
    for (let i = 1; i <= Math.floor(score.length / m); i++){
        box += score[count] * m;
        count += m;
    }
    
    return box;
}

내림차순으로 정렬해주었고 항상 일정하게 한박스에 m개씩 넣어주기 때문에 각 배열의 마지막이 가장 작은 수가 된다.
그러므로 m - 1 (배열은 0부터 시작하기 때문에 -1를 해준다)을 count로 넣어주고 m씩 더해주며 해당하는 인덱스 * m을 박스에 더해준다.