JS Practice) 프로그래머스 Lv.1 : 과일 장수

 

과일장수

문제설명 :

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

 

제한 사항

• 3 ≤ k ≤ 9
• 3 ≤ m ≤ 10
• 7 ≤ score의 길이 ≤ 1,000,000
  • 1 ≤ score[i] ≤ k
• 이익이 발생하지 않는 경우에는 0을 return 해주세요.

 

입출력 예

k	m	score	result
3	4	[1, 2, 3, 1, 2, 3, 1]	8
4	3	[4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]	33

 

첫번째 접근

:  시간 초과로 테스트 11~15를 통과하지 못했다.

// 첫번째 시도
function solution(k, m, score) {
    score = score.sort((a,b) => b-a)
    let sum = 0
    while(score.length >= m){
        sum += Math.min(...score.slice(0, m)) * m
        score = score.slice(m)
    }
    return sum
}

// 두 번째 시도
function solution(k, m, score) {
    score = score.sort((a,b) => b-a)
    let sum = 0
    let arr = []
    while(score.length >= m){
        arr.push(score.slice(0, m))
        score = score.slice(m)
    }
    return arr.reduce((a, c) => a + (c.pop() * m), 0)
}

// 세 번째 시도
function solution(k, m, score) {
    score = score.sort((a,b) => b-a)
    let sum = 0
    const length = Math.trunc(score.length / m);
    for(let i = 0; i < length; i++){
        sum += score.slice(0, m).pop() * m
        score = score.slice(m)
    }
    return sum
}

// 네 번째 시도
function solution(k, m, score) {
    score = score.sort((a,b) => b-a)
    let sum = 0
    let idx = m - 1
    const length = Math.trunc(score.length / m);
    for(let i = 0; i < length; i++){
        sum += score[idx] * m
        idx += m
    }
    return sum
}

 

 

두번째 접근

: 블로그 포스팅을 할때 다시 풀어보려고 하는데, 당시에 문제를 너무 어렵게 접근해서 풀었던것 같다. 

이번에는 score 배열을 내림차순으로 정렬한 후, 해당 m개씩 잘라서 가장 작은 숫자를 sum 변수에 대해주는 방식으로 문제를 해결했다. 한번씩 늪에 빠지는 경우가 있는데, 과일 장수 문제는 당시에 그런 문제였던것 같다.

function solution(k, m, score) {
    let sum = 0
    score = score.sort((a, b) => b-a)
    
    for(let i=0; i < score.length; i+= m){
        if(score.slice(i, i + m).length === m) sum += Math.min(...score.slice(i, i + m)) * m
    }
    
    return sum
}

 

 

solution

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;
}