과일 장수

문제 링크🔗

처음 풀이

첫 코드는 정확도 테스트 24개 중 5개에서 시간 초과였다. while문 안에서 for문을 한 번 더 도는 이중 반복문이 있어 시간 복잡도가 O(N2)(제곱)이 되었다.

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

    while (score.length >= m) {
        let box = [];

        for (let i = 0; i < m; i++) {
            box.push(score.shift());
        }
        
        boxes.push(box);
    }
    
    for (let appleBox of boxes) {
        answer += appleBox.reduce((a, b) => Math.min(...appleBox) * m, 0)
    }
    
    return answer;
}

두 번째 풀이

반복문을 while문 한 개로 줄여 시간 복잡도를 O(N)으로 감소시켰다. 하지만 여전히 같은 정확도 케이스 5개에서 시간 초과가 떴다.

function solution(k, m, score) {
    let answer = 0;
    
    score = score.sort((a, b) => b - a);
    
    let box = [];
    
    while (score.length || score.length >= m) {
        box.push(score.shift());
        
        if (box.length === m) {
            answer += Math.min(...box) * m;
            box = [];
        }
    }
    
    return answer;
}

새로운 풀이

다른 풀이를 참고하여 무조건 앞에서 1개씩만 뺄 수 있는 shift 메서드 대신, splice 메서드를 사용하여 m개를 한 번에 빼낼 수 있었다. (= m개를 뽑았는지 체크하는 if문 분기를 줄임)

splice 메서드는 1번째 항에 음수를 넣으면 뒤에서부터 해당 음수 자리까지 세서 그 위치에서 2번째 항(m)만큼 뒤쪽으로 배열을 잘라준다.

처음에 정렬을 내림차순으로 해줬더니 나중에 sliced의 0번째를 가져오는 로직(시간 복잡도 O(1))이 어렵기도 했고, 내림차순 정렬 후 배열의 마지막 값을 가져오는 .at(-1)과 [sliced.length - 1] 로직 모두 시간 초과가 떠서 최종적으로는 오름차순 정렬을 해준 뒤 splice 메서드를 활용해 뒤에서부터 잘라주었다.

function solution(k, m, score) {
    let answer = 0;
    
    score = score.sort((a, b) => a - b);
    
    while (score.length >= m) {
        let sliced = score.splice(-m, m);
        answer += sliced[0] * m;
    }
    
    return answer;
}