Programmers] 과일 장수

📌 파이썬 으로 풀이

 

📌 문제 링크 : 

프로그래머스

 

📌 문제 설명 :

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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 해주세요.

 

📌 입출력 예

---

추측) 

* 최대한 이익을 위해 상자에 담지 못할 사과는 하품의 사과들로 할 것

- 상자가 몇개 (box) 나오고, 몇개가 버려질지 먼저 계산

- 전체에서 하품들을 어떻게 골라낼 것인가  > sort해서 오름차순으로 정리하여 버려질 개수를 삭제

- 삭제하고 나서의 가장 배열 0번째가 가장 낮은 점수 p에 해당 

- m개식 잘라 상자에 넣고 다음 상자에서 가장 첫 인덱스 값을 또 넣어 p(가장 낮은 점수) x m(한상자 안의 사과수)  결과 값을 구해 result에 계속 더함

- 그리고 result 반환

 

* 이익이 발생하지 않는 경우? > 한상자를 아예 만들지 못하는 경우

* 최대 점수는 왜 있지? 최대 점수를 넘는 사과도 있나?

 

소스코드) 

* 1차) 실패: 79.2 ( 시간초과  11 - 15 케이스)

def solution(k, m, score):
    remain = len(score) % m
    box = int(len(score)/m)
    if box == 0 :
        return 0

    score.sort()
    result = 0
    score = score[remain:]
    for i in range(0, box) :
        p = score.pop(0)
        result += p * m
        for i in range(0, m-1) :
            score.pop(0)

    return result

* 2차) 성공 : 스택으로 풀기

def solution(k, m, score):
    score.sort()
    result = 0

    while int(len(score) / m) > 0 :
        p = 0
        for x in range(0, m) :
            p = score.pop()

        result += p * m

    return result

 

리뷰) 

또 시간 초과가 났길래 스택이나 큐를 사용해볼까 했는데, 역시나... 자료구조를 정말 열심히 공부해야겠다. 자료구조를 잘 알면 쉽게 풀 수 있는 문제를 훨씬 수월하고 효율적으로 풀 수 있음을 느꼈다.  pop이나 푸쉬는 O(1) 이라 시간 복잡도 측면에서 굉장히 좋고, 뭔가 코드 자체도 간결해져서 굳! 👍