프로그래머스 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 해주세요.

 

내 코드

 

def solution(k, m, score):
    answer = 0
    score.sort(reverse=True)
    for i in range(m-1,len(score),m):
        answer += score[i]*m
    return answer

 

m-1 인 이유! 

문제의 핵심: 묶음을 m개씩 처리하는 방법

1. m개씩 묶는 방식이 핵심인데,

• 예를 들어 **m = 3**이면, 3개씩 묶어서 처리해야 해.
• 그럼 score를 내림차순으로 정렬하고, 3개씩 묶어서 그 묶음의 가장 작은 값을 더해야 해.

2. m-1을 사용하는 이유

1) 0-based 인덱스 (0부터 시작하는 인덱스):

• score 배열에서 인덱스는 0부터 시작하잖아. 예를 들어 m = 3이면, 3개씩 묶을 때:
  • 첫 번째 묶음은 score[0], score[1], score[2] → 3개 묶음
  • 두 번째 묶음은 score[3], score[4], score[5] → 3개 묶음
  • ...

2) m-1부터 시작하는 이유:

• 첫 번째 묶음의 가장 작은 값은 score[2] (3번째 값)야.
• 두 번째 묶음의 가장 작은 값은 score[5] (6번째 값)야.
• 이런 식으로, 각 묶음의 마지막 값을 m-1부터 시작하여, m간격으로 선택해야 한다는 거야!

예시: m = 3일 때, score = [6, 5, 4, 3, 2, 1]

1. 0-based 인덱스에서:
   • 첫 번째 묶음: score[0], score[1], score[2] → 마지막 값: score[2] → 3
   • 두 번째 묶음: score[3], score[4], score[5] → 마지막 값: score[5] → 1
2. for i in range(m-1, len(score), m):
   • m-1 → 첫 번째 묶음의 마지막 인덱스(m=3일 경우, 2번째 인덱스)
   • len(score) → 끝까지 반복
   • m → 3개의 값마다 묶어주는 역할