[Algorithm] 과일 장수 (JavaScript - Programmers)

문제 설명

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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) for 방식

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

 

 

 

2) while 방식

function solution(k, m, score) {
    let answer = 0;
    const arr = score.sort((a,b) => b - a)
    let index = m - 1;
    let count = 0;
    const loopLength = score.length;
 
    while(true) {
        if (count + m > loopLength || count >= loopLength) {
            break;
        }
 
        answer += arr[index] * m
        count += m;
        index += m
    }
    return answer;
}

 

 

---

 

 

풀이의 복기

처음에는 while 문으로 로직을 구성했다. 하지만 테스트 11~15번에서 시간 초과가 발생했다.

 

1) 

function solution(k, m, score) {
    let answer = 0;
    const arr = score.sort((a,b) => b - a)
    let count = 0;
    const loopLength = score.length;
 
    while(true) {
        if (count + m > loopLength || count >= loopLength) {
            break;
        }
 
        answer += arr.splice(0, m).pop() * m
        count += m;
    }
    return answer;
}

 

 

 

이유를 고민하고 찾아보다보니 while문에서 for문으로 고침으로써 해결이 됬다고 해서 로직을 변경했다. 하지만 여전히 시간 초과가 발생했다. 문제는 while문과 for문이 아니라 내장함수를 많이 사용한 것이였다. 그래서 함수를 1개만 사용하는 방식으로 변경했다.

 

2)

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

 

 

 

마지막으로, 그렇다면 for 문에서 while 문으로 변경하면 똑같이 통과가 될까? 의문이 들었다.

 

3)

function solution(k, m, score) {
    let answer = 0;
    const arr = score.sort((a,b) => b - a)
    let index = m - 1;
    let count = 0;
    const loopLength = score.length;
 
    while(true) {
        if (count + m > loopLength || count >= loopLength) {
            break;
        }
 
        answer += arr[index] * m
        count += m;
        index += m
    }
    return answer;
}

 

 

 

 

다행스럽게 잘됬다. 그렇다면 생각해볼 수 있는점은 while문과 for문 어떤걸 사용해도 차이는 없다라는 작은 표본을 얻었다. (사실 이후에도 많은 비교를 해봐야지 알겠지만...) 그렇지만, 내장함수들을 많이 사용하는 것은 프로그램의 속도를 떨어트리므로 너무 함수들에 의존해서 만드는것이 좋지않다는것을 느꼈다.