문제 설명
과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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 해주세요.
입출력 예
k:3, m:4, score: [1, 2, 3, 1, 2, 3, 1], result: 8
문제 풀이
첫번째 풀이(시간 초과)
첫번째 풀이는 시간 초과가 발생했으나, 배열을 굳이 정렬시키지 않고 풀었다는 점에 개인적으로 의의를 둔다.
score의 길이만큼 for문을 돌면서 최대값을 구하고 해당 최대값을 score배열에서 삭제하고, 카운트 횟수를 1증가시킨다. 이때 카운트 횟수가 m의 배수인 경우 누적합에 m*최대값 을 더해주면 된다.
이렇게하면 상자에 m개를 담을때 상자의 가격을 최대로 할 수 있게 된다.
def solution(k, m, score):
s_len = len(score)
answer = 0
cnt = 0
for i in range(s_len):
maxS = max(score)
score.remove(max(score))
cnt+=1
if cnt%m == 0:
answer+=m*maxS
return answer두번째 풀이
파이썬 내장함수를 이용하여 손쉽게 배열을 정렬해준다음, m번째 간격으로 index를 뛰어서 해당 index의 값*m 을 누적합에 더해주면 된다.
range함수와 sort함수의 이상적인 조합인 것 같다.
def solution(k, m, score):
answer = 0
score.sort(reverse=True)
for i in range(m-1, len(score), m):
answer+=m*score[i]
return answer