leetcode hard : Maximum Performance of a Team

https://leetcode.com/problems/maximum-performance-of-a-team/

Maximum Performance of a Team - LeetCode

 

n명의 엔지니어 중에 k명을 골랐을 때 (combination이 생각나는가?)

그 k명의 (speed합 * efficiency최소값)의 최대값을 찾아야된다. 

efficiency가 작아도 speed가 높으면 점수가 높게 나올 수 있고 efficiency가 커도 speed가 작으면 점수가 낮게 나올 수 있다는 점에서 머리를 싸매게 만드는 문제다. 그리고 무조건 k명을 고르는게 아니라 "Choose at most k"이므로 k-1, k-2명을 골라도 k명 고르는거보다 점수가 높으면 그 점수를 리턴해야된다.

 

처음 봤을땐 거의 20분간 머리를 움켜잡고 고민했다. 이걸.. 어떻게 풀어야 되지?

뭔가..? (speed, efficiency) 이렇게 묶어서 리스트형태로 관리하면서 one scan으로 최대값 갱신시켜가면서 풀어야될거같은..?

스캔 하기 전에 efficiency 기준으로 sorting을 먼저 해야될거같은..?

 

from heapq import heappush, heappop

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        heap = []
        kspeedsum = 0
        answer = 0
        
        for e,s in sorted(zip(efficiency, speed), reverse=True):
            heappush(heap, s)
            kspeedsum += s
            if len(heap) > k:
                kspeedsum -= heappop(heap)
            answer = max(answer, kspeedsum * e)
            
        return answer % (1000000007)

 

내가 푼 방법은 다음과 같다.

1. (efficiency, speed)를 묶어서 리스트로 만든다.

2. 이 리스트를 efficiency 내림차순으로 정렬한다.

3. 리스트를 스캔(iteration)해가면서 최대값을 갱신한다.

    3.1 현재 보고 있는 원소가 i번째 원소라고 가정하면

    3.2 answer = max(answer, 리스트의 0번째 원소부터 i번째 원소들중에 k개를 골랐을 때 speed합의 최대값 * i번째 원소의 efficiency)

 

즉 지금까지 스캔한 원소들중 speed값의 최대값을 갱신시켜가면서 efficiency를 곱해 점수를 구하고 그 점수가 정답값보다 큰지 작은지 비교해 실시간 갱신하는 방법이다. 현재 원소의 efficiency를 곱하는 이유는 efficiency가 내림차순 정렬되어있으므로 현재 원소의 efficiency가 지금까지 본 원소들 중 가장 작음이 보장되기 때문이다. 그러니까 현재 원소를 포함해서 k개를 고른다면 최대값이 얼마인가?를 계속 갱신해가는거다. 현재 원소를 포함함을 가정하므로 당연히 efficiency 최소값은 현재 원소의 값이 되겠고 efficiency가 고정되었으니 지금까지 본 원소들 중에 k개를 골랐을때 speed합의 최대값이 얼마인지만 알면 최대의 performance값을 계속 갱신해갈수있는것이다. 만약 k개를 골랐는데 거기 현재 원소가 포함이 안돼있으면 어떡하나? 그건 신경쓸 필요없다. 현재 원소를 보기 전에 스캔해오는 과정에서 그 최대값이 이미 계산됐을거기 때문이다. 현재원소는 efficiency가 이전 계산했을때보다 작거나 같을거기때문에 (현재 원소를 포함하지 않는 k개의 speed합) * (현재 원소의 efficiency)는 무조건 이전에 구한 정답값보다 작거나 같을수밖에 없다. 정답값이 이상하게 갱신될일이 없다는 얘기.

 

상당히 까다로운 문제다. 면접때 마주치기 싫은 문제 ㅋㅋㅋ

내가 써놓은 이 말들을 내가 나중에 봤을 때 이해할 수 있을지도 미지수