(H - 1383. Max Perf. of a Team) DP? 그리디?

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

Maximum Performance of a Team - LeetCode

문제를 풀며 적은 사고 과정 정리.

 

배운 점) DP가 왜 안되는지, Greedy 정당성 증명, 내가 생각한 아이디어 구현하는 구현력 기르기 

 

---

'At most' k
-> DP로 모든 경우 탐색 각인데

 

1. BF
C(N, K) -> 말도 안되게 큰 숫자. 무조건 안됨

 

 

---

2. DP
choose(n, k) : idx = n 부터 k명 뽑을 때 max performance
choose(n, k) = max(choose(n+1, k-1) + new_performance, choose(n+1, k)) // 뽑 or 안뽑
어? 근데 performance 구하려면, speed 합 * min_efficiency 필요함.
min_efficiency는 '이전 정보'에 해당
게다가 O(NK) memo 하려면 10^10 메모리 필요 (10GB)

문제점 1) 메모리 → N < K인 경우는 제외, 10^10 / 2
그래도 많은데..

문제점 2) min_eff 정보?
안그래도 메모리 부족한데 배열 하나 더 써??
→ efficiency decreasing order로 정렬해서 관리하면 매번 새로운 사람 뽑을때마다 min_eff 갱신돼서 트래킹 안해도 됨 (Hint 보고 깨달음)

문제점 3) modulo 때문에 max 비교 이상하게 되지 않을까?

정의를 바꿔보자.
choose(n) : n을 뽑았을 때 max perf
k 정보? 역시나 min eff 정보도 여전히 모름. 문제점이 너무 많네.

 

→ 슬슬 DP로는 못풀겠다는 생각이 들었음.

근데 Greedy를 생각해봐도, 뭘 greedy 하게 선택해야하는지 감이 안옴

 

 

---

3. Greedy
Performance = sum(speed) * min(eff)

Try 1)
speed는 덧셈인데
efficiency는 곱셈이라.. efficiency 최대한 높이는게 맞을까? eff 내림차순 정렬해서 top K 뽑기?

반례) N = 4, K = 2
1 2 1000 2000
100 99 2 3

1 2 뽑 -> 3 * 99 
1000 2000 뽑 -> 3000 * 2

느낌상 speed나 eff 순으로 뽑는 그리디는 아닌 것 같은데... 흠

Try 2)
speed * efficiency 순으로 뽑아?
반례) N = 3, K = 2
[10000, 1, 9]
[1, 1001, 1002]
10000 보다는 1, 9를 고르는게 이득임

K번 루프 반복 O(N*K)는 말도 안되고,
efficiency 순으로 정렬한 뒤, 하나 선택하면 그 이전 선택지는 버려도 되나?
-> TC 몇 개 가지고 놀아본 결과, 하나를 시작점으로 선택했을 때, 그 이전 케이스 선택할 때도 있음

 

---

→ 여기까지 1~2시간 정도 고민하고 결국 해답 봄

https://leetcode.com/problems/maximum-performance-of-a-team/discuss/741822/Met-this-problem-in-my-interview!!!-(Python3-greedy-with-heap)

 

1. 일단 K조건을 없애서 간단한 문제를 생각해보자.
efficiency 순으로 내림차순 정렬.
답이 되는 Best team이 있다고 가정하고, 그 팀의 min eff = e_m
그럼, e >= e_m 인 선수들을 모조리 다 편입시키는게 이득이지. speed가 늘어날 수록 e_m이랑 곱해져서 perfomance 커지니까.


2. 이제 K명만 선택한다는 조건을 넣어보자.
반대로 생각하면, 기존 e >= e_m 팀에서 누군가 방출해야 하는 상황.
누구를 방출해야 performance가 최대한 유지될까? 

Case 1) e > e_m 인 사람
> 그 중 speed가 가장 작은 사람 방출

Case 2) 가장 마지막 사람 e_m
> min efficiency가 두번째로 작은 사람이 됨

근데 잘 생각해보면, Case 2는 Case 1에 포함됨을 알 수 있다.
e_m이 speed가 가장 작으면 방출해버리는게 낫다. 
어차피 남은 사람들의 efficiency가 더 크기 때문에.

즉, 우리는 처음에 K 조건 생각하지 않고 Best Team 찾은 뒤,
만약 size > K 라면 speed 가장 작은 사람 순으로 방출하면 된다.
(size <= K 일땐 'at most K' 조건 덕에 그냥 답이 됨)


Q. Best Team에서 몇 명 방출해서 K명 만드는 것 vs 애초에 처음부터 best는 아니지만 K명인 team 구하는 것
둘 중 전자 performance가 더 크다는 걸 증명할 수 있나?
> ㅇㅇ. 후자를 size K인 Team L 이라고 해보자.
Best Team 에서 몇 명 제거해서 size K를 만들어야 하는데, 제거에 두 가지 경우가 있다
1) Team L에 속한 사람을 제거 -> Team L이 optimal 하지 않다는 소리. 제거 결과 Team L보다 뛰어난 performance의 팀이 만들어진다.
2) Team L 바깥에 있는 사람만 제거 -> 제거 결과 결국 Team L이 된다.

 

 

그래서 아이디어 따라 best team 찾고 그 중 K명이 될 때까지 Spd 낮은 사람 방출하는 코드를 짜봄. 결과는 WA

 

# Sol 1) (WA) min e_m 을 제거하게 더 나을수도 (반례)
import heapq
def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
    zipped_lists = zip(speed, efficiency)
    sorted_pairs = sorted(zipped_lists, key = lambda tup : tup[1], reverse = True)
    tuples = zip(*sorted_pairs) # unzip
    speed, efficiency = [ list(tuple) for tuple in tuples]
    
    # Get best team (without K constraint)
    perf = 0
    spd_sum = 0
    min_idx = -1
    for idx, s in enumerate(speed):
        eff = efficiency[idx]
        spd_sum += s
        if spd_sum * eff > perf:
            min_idx = idx
            perf = spd_sum * eff
 
    # init pq and pop people (with lower spd) to meet K
    pq = []
    for idx in range(min_idx+1):
        heapq.heappush(pq, (speed[idx], efficiency[idx]))
    while len(pq) > k:
        heapq.heappop(pq)
 
    # Get result
    pq.sort(key = lambda t : -t[1])
    spd_sum = 0
    for t in pq:
        spd_sum += t[0]
    min_eff = pq[-1][1]
    
    return spd_sum * min_eff

 

반례)
5
[6,6,10,5,8]
[8,2,8,10,6]
3

Before pop [(5, 10), (6, 8), (10, 8), (8, 6)]
(5, 10) 을 없앨게 아니라 (8, 6)을 없애야 답임

Best team 구해두고 spd가 가장 작은 직원 없애는게 아닌가??

---

잘 생각해보니 위에서 Case 2가 Case 1에 포함될 때는, min_idx 사람의 spd가 가장 낮을 때만임.

Case 1과 Case 2를 모두 해보고, performance 잘 나오는 쪽을 선택하도록 구현하면?

-> 그래도 WA 뜨더라.

# Sol 2) (WA) Sol 1의 pop 놓친 부분 고침 - 그래도 WA
import heapq
class Solution:
    def calculate_perf(self, team):
        team.sort(key = lambda t : -t[1]) # min_eff 찾기 위해 무조건 sorting -> 비효율적
        spd_sum = 0
        for spd, eff in team:
            spd_sum += spd
        return spd_sum * team[-1][1]
    
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        # Get best team (without K constraint)
        people = sorted(zip(speed, efficiency), key = lambda tup : -tup[1]) # (spd, eff) in efficiency decreasing order
        perf = 0
        spd_sum = 0
        min_idx = -1
        for idx, (s, eff) in enumerate(people):
            spd_sum += s
            if spd_sum * eff > perf:
                min_idx = idx
                perf = spd_sum * eff
 
                
        # init pq                
        pq = []
        for idx, (s, eff) in enumerate(people):
            if idx > min_idx:
                break
            heapq.heappush(pq, (speed[idx], efficiency[idx]))
 
            
        # Pop people to meet K (2 cases)
        while len(pq) > k:
            cpy = pq[:]
 
            # 1. Spd 가장 낮은 사람 pop
            heapq.heappop(pq)
            perf1 = self.calculate_perf(pq[:])
 
            # 2. min_idx pop
            cpy.sort(key = lambda t : -t[1])
            cpy.pop()
            perf2 = self.calculate_perf(cpy)
 
            if perf1 < perf2:
                pq = cpy
                
        MODULO = int(1e9 + 7) # int 안씌우면 double 처리돼서 % 연산 시 오차 발생
        return self.calculate_perf(pq) % MODULO  

 

그냥 해설 코드 따라서 처음부터 PQ 쓰고, K명 유지한 채로 max performance 업데이트 하는 식으로 구현해서 통과함. 

# Sol 3) 처음부터 PQ 이용, spd 낮은 사람 방출해가며 K명 유지 + max performance 트래킹
class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        people = sorted(zip(speed, efficiency), key = lambda tup : -tup[1]) # (spd, eff) in efficiency decreasing order
        pq = []
        spd_sum = 0
        best_perf = 0 # ans
        for idx, (spd, eff) in enumerate(people):
            # init
            if idx < k:
                heapq.heappush(pq, spd)
                spd_sum += spd
            # replace min spd with higher spd, but with lower eff (this may result in lower or even 'higher' performance)
            elif spd > pq[0]:
                spd_sum = spd_sum + spd - heapq.heappushpop(pq, spd)
 
            best_perf = max(best_perf, spd_sum * eff)
        
        MODULO = int(1e9 + 7) # int 안씌우면 double 처리돼서 % 연산 시 오차 발생
        return best_perf % MODULO