[2024] day 171. Leetcode 826. Most Profit Assigning Work

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 18일 (화)
Leetcode daily problem

826. Most Profit Assigning Work

https://leetcode.com/problems/most-profit-assigning-work/?envType=daily-question&envId=2024-06-18

Problem

n개의 jobs와 m개의 workers가 있다.
여기서는 difficulty, profit, workers의 배열 세 개가 주어진다.

• difficulty[i]와 profit[i]은 i번째 작업의 난이도와 이익이고,
  workers[j]는 j번째 작업자의 능력입니다(즉, j번째 작업자는 대부분의 작업자[j]에서 difficulty가 있는 작업만 완료할 수 있다).
• 모든 작업자는 최대 하나의 작업에 할당될 수 있지만 하나의 job은 여러 번 완료할 수 있다.

예를 들어, 세 명의 근로자가 1달러를 지불하는 동일한 작업을 시도하면 총 이익은 3달러가 된다. 근로자가 작업을 완료할 수 없으면 수익은 $0이다.
worker들을 작업에 할당한 후 달성할 수 있는 최대 이익을 반환한다.

Solution

greedy

worker 각각이 수행할 수 있는 작업 중 최대 이익을 얻을 수 있도록 할 때 모든 worker가 얻을 수 있는 총 이익을 구하는 과정에서
난이도가 낮은 작업부터 높은 순으로 접근할 수 있도록 difficulty를 오름차순으로 정렬한다.
worker를 기술 수준에 따라서 오름 차순으로 정렬한다음, 각 근로자가 수행할 수 있는 작업 중 최대 이익을 찾는다.
정렬된 작업과 profit을 활용해 근로자에게 최대 이익을 할당하고 전체 얻을 수 있는 profit을 업데이트 하여 반환한다.

Code

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        worker.sort()
        jobs = sorted(zip(difficulty, profit))
        
        maxProfit = 0
        totalProfit = 0
        i = 0
        
        for skill in worker:
            while i<len(jobs) and jobs[i][0] <=skill:
                maxProfit = max(maxProfit, jobs[i][1])
                i+=1
            totalProfit += maxProfit
            
        return totalProfit

Complexicity

시간 복잡도

difficulty, profit의 리스트를 하나로 만드는데 O(n)이 소요되고, 이를 정렬하는데 O(nlogn)이 소요된다. 또한 worker 배열을 정렬하는데 각 O(mlogm)이 소요된다.
모든 worker를 순회하면서 최대 이익을 찾기 때문에 O(n+m) 의 시간이 소요된다. 즉 전체 시간 복잡도는 O(n+m) + O(nlogn) 이다.

difficulty, profit의 job 의 배열의 길이 n, worker의 길이 m
최대 이익 계산 O(n+m)

공간 복잡도

두 배열을 합쳐서 새로운 리스트를 만드는 추가적인 O(n)이 필요하다.
나머지는 상수 변수를 할당하므로 최종 공간복잡도는 O(n) 이다.