[Greedy]99클럽 코테 스터디 19일차 TIL + 프로그래머스/1/135808. 과일 장수

문제 설명

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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	m	score	result
3	4	[1, 2, 3, 1, 2, 3, 1]	8
4	3	[4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]	33

---

입출력 예 설명

입출력 예 #1

• 문제의 예시와 같습니다.

입출력 예 #2

• 다음과 같이 사과 상자를 포장하여 모두 팔면 최대 이익을 낼 수 있습니다.

사과 상자	가격
[1, 1, 2]	1 x 3 = 3
[2, 2, 2]	2 x 3 = 6
[4, 4, 4]	4 x 3 = 12
[4, 4, 4]	4 x 3 = 12

따라서 (1 x 3 x 1) + (2 x 3 x 1) + (4 x 3 x 2) = 33을 return합니다.

 

 

 

<내코드> : 40분

def solution(k, m, score):
    # k == 사과의 최대점수
    # m == 한개 상자에 사과의 수
    # score == 사과의 점수들
    
    # 리스트 오름차순 정렬
    score.sort()
    
    price = 0
    apple_box = []
    # while m - 1 < len(score) : 
    
    # 박스 갯수 이하인 경우에도 일단 모두 pop 해보기!
    while 0 < len(score)  :
        apple_box.append(score.pop())
        
        # apple_box 가 꽉차면은 price 대입하기
        if len(apple_box) == m:
            price += min(apple_box) * m
            apple_box = []
    return price

- 문제를 전반적으로 풀어보면서 풀수있는 환경이 제약되어서 최대한 접근방법부터 먼저 고민했음

- 그 결과 이전에 풀었던 다양한 아이디어가 발산하여 헤매지않고 손쉽게 풀 수있게 되었음

 

1. 헷갈린 부분

- 특정 범위로 각각의 list 가 있는지 검토

=> 기존에는 score라는 list에서 여러 잘려진 list를 각각 모두 list에 담으려고했음 (그러다보니 max()로 계속 끊으려고 했음

=> 하지만 몇번의 방식을 통해 그럴필요없이 곧바로 이용후 비우는 방법을 이용함

=> 하지만 보다 바람직한 방법으로, 리스트 슬라이싱으로 특정범위의 리스트를 하나의 리스트처럼 쉽게 이용이 가능함

 

 - 아쉬운 것?

한땀한땀 pop()을 하기 보다 슬라이싱을 이용하면 보다 쉽게 할 수 있음

 

<모범사례>

def solution(k, m, score):
    # 점수를 내림차순으로 정렬합니다.
    score.sort(reverse=True)
    
    # 최대 이익을 저장할 변수
    max_profit = 0
    
    # m개씩 그룹으로 묶어 가격을 계산
    for i in range(0, len(score) - m + 1, m):
        # 그룹에서 최저 점수와 상자의 수량을 곱해 상자 가격을 구하고 이를 총 이익에 더합니다.
        max_profit += score[i + m - 1] * m
        
    return max_profit

 - score 의 리스트를 내림차순으로 하여서 아래쪽에 이용될 반복문에 그리디 알고리즘을 쉽게 적용하기 위해서 내림차순 정렬함

 

- 반복문을 이용하더라도, m 만큼 간격을 넓혀서 반복을 함 이렇게 하면 리스트 슬라이싱을 용이하게 가능함

 

 

 

 

<보충학습>

 1. 실무에서의 그리디 알고리즘 사용사례

- ERP에서 제한된 자원 분배하기 위해서 적용가능

- 데이터 순서를 정렬해서 그룹화 하는 경우에 이용이 많이 됨 (즉 정렬과 슬라이싱)

 

 2. 추가 연습문제

# 1. 문제 1: 특정 구간의 합 계산하기
list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
start, end = 2, 5

sum = sum(list[start : end + 1]) # 1을 더해야
print(sum)

# 2. 리스트 슬라이싱을 이용한 역순 정렬
list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
start, end = 2, 6

list2 = list[start : end + 1][::-1] #슬라이싱 한번에 두개 가능
result = list[:start] + list2 + list[end+1:] # 해당부분 이렇게 합치기 가능

print(result)

print("3")
# 3.
list = [1, 2, 3, 4, 5]
num = 3

for i in range(num):
    print(list[i: i + num])

- 슬라이싱에다가 sum()연산하는방법

- 슬라이싱에 곧바로 역으로 바꾸는것 한번에 하기

- 붙여버리기

 

등 다양한방식으로 슬라이싱을 더 용이하게 이용할 수있게 됨