과일 장수

문제 설명

과일 장수가 한 상자를 m개씩 포장하고 있다고 한다. 한 상자 마다 점수가 부여되는데, 점수 산정 방식은 해당 상자의 사과 중 제일 작은 점수 사과의 갯수 m 상자의 갯수이다. 과일 장수가 만들 수 있는 최대값을 구하시오.

문제 풀이

첫 번째 접근

문제를 보자마자 정렬을 해서 풀어야겠다고 생각했다. 그러나 갑자기 든 생각. 만일 가장 값이 큰 과일이 각 상자에 들어가면 어떻게 될까? 정답은 안 된다!

프로그래머스에서 든 예시를 보자.

[1, 1, 2][2, 2, 2]
[4, 4, 4][4, 4, 4]

이렇게 과일 상자가 있을 때 점수가 4인 사과를 맨 윗 상자와 위에서 두 번째 상자로 옮겨준다고 하면 상자는 아래처럼 될 것이다.

[4, 1, 2][4, 2, 2]
[1, 4, 4][2, 4, 4]

해당 상자에서 최솟값을 구하는 문제이기에 최솟 값은 차례대로 1, 2, 1, 2가 된다. 그러면 초기 값보다 더 작은 수가 나오기 때문에 이렇게 풀어주면 안 된다.

두 번째 접근

그렇다면 일단 배열을 정렬하도록 한다. 여기서 나는 배열을 내림차순으로 정려했다.
그리고 정렬한 사과 배열을 m개만큼 자른다. 만일 자른 박스의 길이가 기준인 m보다 지금까지 구한 사과의 수가 범위보다 크면 break를 한다.

그렇지 않으면 box의 맨 마지막 값(어차피 내림차순 배열이라 최소 값은 마지막에 있다)과 m을 곱해준다. 그리고 그 값을 answer와 더해주면 끝!

코드

python

def solution(k, m, score):
    answer = 0
    score.sort(reverse = True)
    count = 0
    
    while True:        
        box = score[count:count+m]
        
        if count >= len(score) or len(box) < m:
            break
        
        tmp = box[m-1]*m
        answer += tmp
        count += m
    
    return answer