과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.
01 score([4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2])를 sort 하고
02 m(3)으로 나누고 = [4, 4, 4], [4, 4, 4], [2, 2, 2], [2, 1, 1]
03 생성된 상자의 최저값 곱하기 m x 상자의 개수 = 24 + 6 + 3 = 33
function solution(k, m, score) {
let answer = 0
let count = Math.floor(score.length/m)
score.sort((a,b) => b-a)
for(let i=0; i < count; i++) {
answer += score.slice(0,m)[m-1]*m
score.splice(0,m)
}
return answer
}
시간초과가 발생하는 이유는 제한사항을 볼 때 7 ≤ score의 길이 ≤ 1,000,000
이고, 3 ≤ m ≤ 10
이라고 하면 극단적인 상황에서 333번의 반복문을 실행하며 slice와 splice를 실행해야 하기 때문이다. 더 효율적인 접근 방식이 필요하다.
꼭 slice를 2번이나 실행해야 할까? 배열을 잘라내는 대신 인덱스를 활용해서 접근할 수는 없을까?
function solution(k, m, score) {
let answer = 0;
score.sort((a, b) => b - a);
for (let i = 0; i < Math.floor(score.length / m); i++) {
answer += score[(i+1)*m - 1] * m;
}
return answer;
}
count
와 score.sort()
까지는 기존과 동일하다. 달라진 부분은 배열을 잘라내는 것이 아니라 count 만큼 정렬된 배열의 해당 인덱스에 접근하는 것이다.
만약에 score의 길이가 20이고, m이 3이라고 하자.
인덱스에 접근하여 배열을 가공할 필요없이 요소를 탐색하며, 증가연산자를 통해서 answer를 수정하고 해당 결과를 도출해내기에 보다 빠른 접근이 가능해진 것이다.