과일 장수

[문제설명]

[제한사항 & 입출력 예]

[문제풀이]

주어진 배열을 내림차순으로 정렬한 후
반복할 숫자 즉 상자 수를 구했고,

score배열을 m-1개씩 짤라서
짜른 마지막 배열이 최소 숫자이기 때문에
그 숫자를 최저 사과 금액으로 계산하고 * m(사과 갯수) x 1
을 해주어서 price(이윤)에 더해줬다
이후 score배열의 0부터 m개 바로 전까지 제거해줬다.

테스트 케이스는 통과했지만 시간초과로 실패!

내가 푼 답

function solution(k, m, score) {
    // 높은 숫자 순으로 정렬
    score.sort((a,b)=>b-a);
    // 반복할 숫자 
    let repeatCount = Math.floor(score.length / m);
    // 이윤
    let price = 0;
    for(let i = 0; i < repeatCount; i++){
        price += score[m-1] * m * 1;
        score.splice(0,m);
    }
    return price;
}

결과

이유

splice를 사용하여 매 반복마다 배열의 처음 m개의 요소를 제거하고 있다.
배열의 처음에서 요소를 제거하는 작업은 O(n) 시간 복잡도를 갖는다.
따라서 배열의 길이가 커질수록 작업이 비효율적이다.
이로인해 전체 시간 복잡도가 O(n^2)로 증가하게 된다.

해결 방법

배열을 슬라이스하여 새로운 배열을 생성하고 그 배열에서 최소 점수를 계산하는 것이 더 효율적이다. splice를 사용하여 새로운 배열을 생성하면
원본 배열을 변경하지 않고도 작업할 수 있다.

수정한 풀이

function solution(k, m, score) {
    // 높은 숫자 순으로 정렬
    score.sort((a,b)=>b-a);
    // 반복할 숫자(상자 수)
    let boxCount = Math.floor(score.length / m);
    // 이윤
    let profit = 0;
    for(let i = 0; i < boxCount; i++){
        // 현재 상자에 담을 사과의 배열
        const box = score.slice(i*m, (i+1) * m);
        const minScore = Math.min(...box);
        profit += minScore * m
    }
    return profit;
}

다른 사람 풀이

function solution(k, m, score) {
    let answer = 0;
    const sortedScore = score.slice().sort((a, b) => a - b).slice(score.length % m);
    for (let i = 0; i < sortedScore.length; i += m) {
        answer += sortedScore[i] * m;
    }
    return answer;
}

깔끔하다..
나는 내림차순으로 정렬 후 풀었는데
이 사람은 오름차순으로 정렬하고 slice해서 상자에 담기지 않은 사과를 빼줬다.
i += m 이걸 사용했다면 반복할 숫자를 따로 구하지 않았어도 될 것 같다.
또 한번 배워간다.