프로그래머스 - 과일 장수

 

문제

 

풀이

처음 풀고자 했던 의도는 score 배열을 내림차순으로 정렬한 뒤, 0번째 인덱스부터 m개씩 만큼 뽑아 최솟값을 구한뒤 m을 곱한 값들을 다 더하면 될 거라고 생각했다

function solution(k, m, score) {
    let answer = 0;
    let slicedScore = [];
    
    // 내림차순 정렬
    score.sort((a, b) => b - a);
    for(let i = 0; i < score.length; i++){
    	// 0혹은 m번째 인덱스면서 score.length-i가 m-1보다 크다면 즉, 남은 개수가 m개 이상일 때
        if((i%m===0) && (score.length-i > m-1)) {
        	// score 배열의 i번째 인덱스 값부터 i+m-1번째 인덱스 값까지 뽑아 최소값*m 푸쉬 
            slicedScore.push(Math.min(...score.filter((_, idx) => idx >= i && idx <= i+m-1))*m);
        }
    }
    // slicedScore 배열요소들의 합
    return slicedScore.reduce((cal, cur) => cal + cur);
}

 

하지만, score 배열의 최대 길이가 100만인 조건 때문에 for문 안의 Math.min과 filter는 효율이 굉장히 좋지 못했다

처참한 효율

 

두번째 풀이

풀이법을 다시 고민하던 와중 push와 pop을 할 때 시간복잡도는 O(1)이라는 사실을 알게 되어서 push와 pop을 활용하기로 했다

function solution(k, m, score) {
    let answer = 0;
    
    // score 배열 오름차순 정렬
    score.sort((a, b) => a - b);
    
    // score 배열 길이가 m보다 작아질 때 까지 반복
    while(score.length >= m) {
        let initArray = [];
        // score 배열의 마지막요소를 뽑아 initArray에 푸쉬
        for(let i = 0; i < m; i++){
            initArray.push(score.pop());
        }
        // initArray의 마지막 요소 * m 을 answer에 더해준다
        answer += initArray[initArray.length-1]*m;
    }
    return answer
}

good