Leetcode 826. Most Profit Assigning Work

문제

You have n jobs and m workers. You are given thr
ee arrays: difficulty, profit, and worker where:

difficulty[i] and profit[i] are the difficulty and the profit of the ith job, 
and worker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]).
Every worker can be assigned at most one job, 
but one job can be completed multiple times.

For example, if three workers attempt the same job that pays $1, 
then the total profit will be $3. If a worker cannot complete any job, 
their profit is $0.
Return the maximum profit we can achieve after assigning the workers to the jobs.

1. n개의 직업과 m명의 직원이 있다.
2. 각각의 직업엔 난이도와 이익이 있고, 각 직원은 자신이 할수 있는 난이도의 최대치가 있다.
3. i번째 difficulty 는 i번째 직업의 난이도, i번째 profit 은 i번째 직업의 이익이 있고,
   j번째 worker의 값은 그 직원이 할수 있는 최대한의 난이도를 뜻한다.
   - 즉 5만큼 할수 있는 사람은 최대 5 난이도의 직업을 선택할수 있다.
4. 한 직업 여러사람이 맡을수 있고, 맡은 모든 사람이 같은 이익을 얻을수 있다.
5. 최대한 많은 이익을 얻을때, 이익을 구하시오.

예시

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation:
    - 4, 5 직원은 각각 20의 이익을 얻는 직업을 진행한다.
    - 5, 6 직원은 각각 40의 이익을 얻는 직업을 진행한다.
    - 20 + 20 + 40 + 40 = 총 120 의 이익을 얻을수 있다.

제한

• $n == difficulty.length$
• $n == profit.length$
• $m == worker.length$
• $1 <= n, m <= 10^4$
• $1 <= difficulty[i], worker[i] <= 10^5$

풀이법

1. 먼저 나뉘어져 있는 difficulty 와 profit 을 하나로 묶기 위해 Job 클래스를 만들었다.
2. selectedJob 을 두고 difficulty 와 profit을 각각 0으로 만들었다.
3. Job의 배열로 받은 값들을 수정하고, 배열의 값을 difficulty 가 오름차순이 되도록 정렬한다.
4. Worker 의 배열도 오름차순이 되도록 정렬한다.
   • 즉, Job과 Worker 둘다 오름차순이 된다.
5. Worker에서 for loop를 돌린다.
   • 주어진 worker가 할수 있는 가장 큰 직업을 저장해 총 이익에 더한다.

• 구한 총 이익 리턴

class Job:
    def __init__(self, diff: int, prof: int):
        self.diff = diff
        self.prof = prof
    def __str__(self):
        return f"diff : {self.diff} || prof : {self.prof}"

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = [Job(diff, prof) for diff, prof in zip(difficulty, profit)]

        jobs.sort(key=lambda k: k.diff)

        worker.sort()

        jobp = 0

        selectedJob: Job = Job(0, 0)

		# 계산할 총 이익
        count = 0

		# 모든 worker에 대해 루프
        for w in worker:
        	# 비교할수 있는 직업이 남아있고, 난이도에 적합하다면
            while jobp < len(jobs) and w >= jobs[jobp].diff:
            	# 선택된 직업의 이익과 가능한 직업의 이익을 비교 및 이익이 더 크다면 선택된 직업을 그 직업으로 수정한다.
                if selectedJob.prof < jobs[jobp].prof:
                    selectedJob = jobs[jobp]
                jobp += 1
            # 총 이익에 더한다.
            count += selectedJob.prof

        return count

포인트

• 모든 worker가 어떤 직업도 선택하지 못할수도 있다. selectedJob은 기본적으로 가장 쉬우면서 가장 이익이 없는 직업으로 설정한다.
  • Job(0, 0)