20230628 TIL

프로그래머스 1단계 과일장수

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.
한 상자에 사과를 m개씩 담아 포장합니다.상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.
과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)

나의 풀이

일단 사과 박스에 들어가는 사과들의 배열을 만들어야 한다고 생각했다. 배열에 직접 영향을 주는 splice()를 사용해서 score를 내림차순으로 정렬한 배열을 m개씩 잘라서 list에 넣었다. list에서 가장 마지막 숫자가 가장 낮은 점수이기 때문에 list[m-1]에 m 을 곱해서 answer에 더해주었다. 

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

하지만 시간복잡도에서 터져버렸다.. 범위를 다시 확인해보니 score의 길이가 1,000,000까지 커질 수 있었다. 이렇게되면 최대 score의 길이가 백만일 때 splice를 하면 시간이 너무 오래 걸리는 문제가 생긴다. splice는 기존의 배열에 있는 값을 갖고 또 다른 배열을 만들어야 하기 때문에 모든 배열을 순회하면서 index 재부여를 해야한다. 이 과정에서 시간복잡도가 O(n)이 나온다.

해결한 방법

splice가 문제라면 안쓰면 된다. 내가 실질적으로 필요한 값은 splice로 자른 배열이 아니라 그 배열내에 있는 가장 작은 값이기 때문이다. 그렇다면 그냥 배열내에서 m 개씩 건너뛰면서 나오는 값만 뽑아서 다 더해주면 된다.

function solution(k, m, score) {
    var answer = 0;
    const scoreList = score.sort((a,b) => b-a)
    const num = Math.floor(score.length / m)
    let list = []

    for (let i = 0;i<num;i++){
        list.push(scoreList[i*m + (m-1)])
    }
    
    list.forEach((item) => {
        answer += item * m
    })
    return answer;
}

다른 사람 풀이

다른 사람의 풀이 중 내가 짠 코드와 흐름은 비슷하지만 더 간결한 풀이가 있었다. 나도 코드를 더 간결하고 가독성이 좋게 짜도록 노력해야 겠다......................ㅠ

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