[파이썬] 프로그래머스 - 과일 장수 (Lv1, Python)

문제 : Programmers-과일 장수

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘 개념

• 정렬, 그리디
  
  • 그리디로 접근해서 풀 수 있다. 그리디 접근을 위해 정렬이 필요하다.

 

풀이

  사과의 개수가 n개라고 해보자. 그렇다면 n%m 개 만큼은 버려져야 한다. 이 때 버려져야 하는 사과는 당연히 점수가 가장 낮은 사과들이다. 또한 이 문제는 m개씩 담은 상자에서 가장 점수가 낮은 사과를 기준으로 가격이 정해진다. 이 때 m개씩 짝지었을 때 낮은 사과가 가장 높게 나오는 방법은 내림차순으로 정렬 후 m개씩 고르는 방법이다(그리디).

 

  위의 두 가지 모두 내림차순으로 정렬 후, m개씩 짝짓고 남는건 버리는 규칙에 부합한다. 따라서 len(score)//m 번만큼 루프를 돌면서 해당 그룹에서 가장 점수가 낮은 녀석(score[i * m + m - 1])을 기준으로 점수를 구해서 리턴해주면 된다.

 

 

코드 : github

#문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
def solution(k, m, score):
    answer = 0
    score.sort(reverse=True)
    for i in range(len(score) // m):
        answer += score[i * m + m - 1] * m
    return answer