프로그래머스 과일 장수 문제풀이 과정, 알고리즘 최적화

프로그래머스 과일 장수 문제풀이 과정, 알고리즘 최적화

 

 

프로그래머스 시저함수 문제 소개와 필자의 문제풀이 및 인기 있는 문제풀이 소개와 해설을 소개하겠습니다. 아래 풀이 과정을 보면서 많은 인사이트를 얻어가시길 바랍니다.

 

 

프로그래머스 과일 장수 문제

 

프로그래머스

 

문제 설명

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

 

 

 

 

필자의 문제풀이

function solution(k, m, score) {
  let answer = 0;
  let apple_arr = score.sort((a, b) => b - a);

  while (true) {
    if (apple_arr.length < m) return answer;

    let temp = apple_arr.slice(0, m);

    answer += Math.min(...temp) * m;

    apple_arr = apple_arr.slice(m);
  }
}

 

이렇게 코드를 만들고 검사를 해보니 '시간초과' 오류가 떴었습니다. 원인은 temp 변수에서 slice 메소드를 사용하면서 배열 길이가 매번 변하게 되어 성능이 저하되고 있던 점 때문이었습니다. 

 

이 문제를 해결하기 위해 temp지정과 루프문 수정으로 최대 이익을 찾는 방향을 택했습니다. 

 

 

수정한 필자 문제풀이

function solution(k, m, score) {
  let answer = 0;
  let apple_arr = score.sort((a, b) => b - a);

  let i = 0;
  while (i < apple_arr.length) {
    let box = apple_arr.slice(i, i + m);
      
    if (box.length < m) break;
      
    answer += Math.min(...box) * m;
    i += m;
  }

  return answer;
}

 

 

 

 

수정된 코드와 기존 코드 간의 차이점은 기본적으로 while 루프의 조건과, 상자에 사과가 충분한지를 체크하는 부분입니다.

 

루프 조건:

• 기존 코드: while (true)로 항상 무한 루프를 돌면서 조건을 체크.
• 수정 코드: while (i < apple_arr.length)로 배열의 길이만큼만 루프를 돌도록 함.

 

상자에 사과가 충분한지 체크:

• 기존 코드: if (apple_arr.length < m)로 상자에 사과가 충분하지 않으면 루프를 빠져나감.
• 수정 코드: if (box.length < m)로 상자의 길이를 체크하여 사과가 충분하지 않으면 루프를 빠져나감.

 

이렇게 수정함으로써, 루프가 필요한 상황에서만 돌고, 루프 내에서도 상자의 길이를 체크하여 충분한 사과가 없으면 루프를 빠져나가도록 구성되었습니다. 이로써 코드의 효율성이 향상되어 불필요한 루프를 도는 것을 방지할 수 있었습니다.

 

▼ 인기있는 다른 코딩테스트 풀이 ▼

 

프로그래머스 문자열 다루기 기본 해설, 인기 있는 문제풀이

 

프로그래머스 시저함수 문제 풀이, 해설, 알고리즘 코딩테스트