[LV.3] 연습문제 > 과일 장수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/135808

프로그래머스

---

문제 설명

• 사과 상자 포장 최대 이익 계산
  - 과일 장수가 사과를 상태별 점수로 분류하여 상자에 포장해 판매하려는 상황
  - 사과는 1점부터 k점까지의 점수로 나뉘며, 점수가 높을수록 품질이 좋음
  • 한 상자에는 m개의 사과를 담음
  • 상자 가격은 가장 낮은 점수 × m 으로 결정됨
  • 사과는 상자 단위로만 판매되며, 남는 사과는 버림
•  점수 리스트가 주어졌을 때, 최대한 많은 사과를 상자로 만들어 판매했을 때의 최대 이익 구하기
• 제한사항
  3 ≤ k ≤ 9
  3 ≤ m ≤ 10
  7 ≤ 사과 개수 ≤ 1,000,000 (사과 점수는 항상 1 이상 k 이하)
• 이익이 발생하지 않는 경우에는 0을 return

---

정답 코드

def solution(k, m, score):
    # 상자를 하나도 만들 수 없는 경우 바로 종료
    if len(score) < m:
        return 0

    # 점수를 내림차순 정렬하여 높은 점수부터 상자 구성
    score.sort(reverse=True)
    answer = 0

    # m개씩 묶어 상자 구성
    for box_start in range(0, len(score) - m + 1, m):
        box_min = score[box_start + m - 1]  # 해당 상자에서 가장 낮은 점수
        answer += box_min * m

    return answer

---

첫 번째 시도 (성공. 개선 필요)

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

---

개선점

 

• box 리스트를 매번 새로 만들어 채우고 min() 사용:
  • 정렬된 리스트에서 상자의 최솟값은 항상 score[m*i + m - 1]로 바로 알 수 있음
  • min(box)는 O(m) 시간이 걸리지만, 그냥 인덱싱하면 O(1)에 해결
• * 1은 불필요한 곱셈:
  • min(box)*m*1 → 그냥 min(box)*m 또는 더 나은 방법은 위에 말한 인덱스로 최솟값 바로 접근