오늘의 코딩 테스트 한줄 - 과일 장수

Edwin·2023년 6월 2일
0
post-thumbnail

오늘의 코딩 테스트 한줄 - 과일 장수

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

문제해석과 풀이

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

countscore.sort()까지는 기존과 동일하다. 달라진 부분은 배열을 잘라내는 것이 아니라 count 만큼 정렬된 배열의 해당 인덱스에 접근하는 것이다.

  • score[(i+1)*m - 1]

만약에 score의 길이가 20이고, m이 3이라고 하자.

  • count = 6, 즉 6번 반복문이 실행될 것이다.
    01 score[(0+1)*3-1] = score[2] => 배열의 3번째 요소
    02 score[(1+1)*3-1] = score[5] => 배열의 6번째 요소
    03 score[(2+1)*3-1] = score[8] => 배열의 9번째 요소 ...

인덱스에 접근하여 배열을 가공할 필요없이 요소를 탐색하며, 증가연산자를 통해서 answer를 수정하고 해당 결과를 도출해내기에 보다 빠른 접근이 가능해진 것이다.

profile
신학전공자의 개발자 도전기!!

0개의 댓글

Powered by GraphCDN, the GraphQL CDN