[프로그래머스] 과일 장수(Python)

문제 링크

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

프로그래머스

소스 코드

def solution(k, m, score):
    score = sorted(score) # 오름차순 정렬
    answer = 0
    # 전체 개수를 m으로 나눈 몫만큼
    for i in range(len(score)//m):
        # m개씩 pop
        for j in range(m-1):
            score.pop()
        # 정렬했으므로 마지막으로 pop하는 것이 최솟값
        answer += score.pop() * m
    return answer

해설

• 그리디 유형
• 시간복잡도 고려

시간복잡도 & 그리디

이 문제도 이전과 마찬가지로 시간복잡도를 미리 고려하는 것이 좋습니다.

사과의 점수가 담긴 리스트 score의 최대 길이가 1,000,000이므로 만약 슬라이싱이나 인덱싱으로 접근하게 된다면 연산 속도가 굉장히 느려질 가능성이 높습니다.

따라서 정렬을 단 한 번만 수행하고 pop 함수를 이용하여 아주 빠른 속도로 문제를 처리할 수 있습니다.

(글을 작성하다가 직접 비교해보니 그냥 인덱싱 한 번으로 접근하는것이 더 빠릅니다. pop 함수를 m번 사용하는 것이 인덱싱 한 번보다 빠르지는 않지만 인덱싱을 m번하는 것보다는 빠를 수 있습니다. 이는 테스트 케이스별로 확인하는 것이 좋겠습니다.)

 

1) 왜 정렬을 해야 할까? -> 그리디

문제에서는 m개씩 묶어 상자를 만들고 이 상자에 포함된 가장 작은 값을 기준으로 상자의 가격이 책정된다고 했습니다.

가지고 있는 모든 사과를 최대한 많이 이용해 상자를 만들되, 상자의 최솟값이 가장 커지는 조건이 무엇인지 생각해야 합니다.

직관적으로 생각해보면 정렬된 리스트에서 가장 큰 값들만 순서대로 뽑아 가는 경우, 각 묶음의 최솟값을 합한 값이 가장 커질 것입니다.

 

예는 다음과 같습니다.

list = [1,1,1,2,2,2,3,3,3,4,4,4] 으로 정렬되어 있다고 가정하고 이를 두 개씩 나누는 경우를 생각해봅니다.

case1 = (1,2),(1,3),(2,3),(1,3),(2,4),(4,4) => 최솟값 : 1,1,2,1,2,4 => 합 : 11

case2 = (4,4),(4,3),(3,3),(2,2),(2,1),(1,1) => 최솟값 : 4,4,3,2,2,1 => 합 : 16

정렬된 리스트를 기준으로 큰 값들을 뽑아 오는 것이 곧 각 묶음의 최솟값을 최대로 늘려줄 수 있다는 것을 이해할 수 있습니다.

따라서 각 경우에 대한 최적의 값을 누적시키는 것이 전체의 최적이 되므로 그리디 유형이라고 볼 수 있겠습니다.

 

2) 왜 pop을 써야 할까?

우선 리스트의 길이를 m으로 나눈 몫만큼 반복문이 돌아간다는 것은 생성할 수 있는 박스 묶음의 개수라고 이해하면 됩니다.

그렇다면 왜 pop을 써야 할까요?

pop 함수는 시간복잡도가 O(1)로 아주 빠르게 수행됩니다.

따라서 리스트의 길이가 아무리 길더라도 한 번 최솟값을 구하는데 O(m)만큼의 시간이 걸리는 것입니다.