[Leetcode]826. Most Profit Assigning Work

문제 요약

• 알고리즘 분류: Two Pointer
• 난이도: Medium
• 문제내용:
  • • difficulty, profit, worker 있다.
    • dificulty[i]는 난이도이고 profit[i]는 diffculty[i]수행시 보상이다.
    • worker는 일하는 사람 최대 할수 있는 난이도를 나타내고 diffculty 이하만 수행 할수 있다.
    • worker들이 최대 보상 받을수 있는 합친 값을 나타 내어라
• 사이트 주소: https://leetcode.com/problems/most-profit-assigning-work/description/

문제풀이

 이번 문제는 브루드포스 같은 모든 경우의 수로 풀면 시간 초과가 난다. 그래서 최적의 시간 복잡도를 돌려야 하는 투포인트 문제이다. 투 포인터 대한 설명은 아래글에 참고하여라

https://jih3508.tistory.com/235

[알고리즘 이론] 투 포인터(Two Pointers)

 

 투 포인터를 어떻게 해결할 방법은 worker와 difficulty 관계를 활용 할 것이다. worker가 difficulty 이하까지 탐색 하면서 진행 하면된다. 그리고 만약에 이전 difficulty보다 보상이 적을 수 있어서 최대 난이도에 따른 보상을 저장 하는것이 아니라  difficulty 탐색하면서 각 worker들이 최대 보상 탐색하면서 추가 해야 한다. 이렇게  two pointer로 구현 하면 각 worker들이 difficulty를 탐색 할 필요 없이 최소한의 탐색으로 답을 찾을수 있다.

 이렇게 구현 하면 시간 복잡도는 O(NlogN)만큼 나올것이다. woker와 difficulty 탐색은 O(N)만큼 나오지만 two pointer 탐색하기 위해서는 worker와 difficulty 정렬해야 한다. 그래서 정렬하는 것때문에 시간 복잡도는  O(NlogN)나온다.

Code

Python

class Solution:
    def maxProfitAssignment(self, difficulty: list[int], profit: list[int], worker: list[int]) -> int:

        # difficulty, profit 하나의 리스트로 재 정의
        jobs = [(d, p) for d, p in zip(difficulty, profit)]
        # difficulty 기준으로 정렬
        jobs.sort(key=lambda job: job[0])
        # worker  정렬
        worker.sort()

        size = len(jobs)
        i = 0
        maxValue = 0 # 이전 profit보다 작을수 있어서 worker 들이 최대 받을수 있는 값을 저장 하기 위한 변수 이다.
        result = 0
        for w in worker:
            # two point
            # worker가 joibs 다 탐색 안하고 이전 탐색부터 시작해서 최대 할수 있는 난이도까지 간다.
            while i < size and w >= jobs[i][0]:
                # 만약 이전 난이도 보다 profit이 적을 수 있어서 이전 profit이랑 비교해서 현재 difficulty까지 최대 값을 저장한다.
                maxValue = max(maxValue, jobs[i][1])
                i += 1
            # 최대 할수 있는 작업 탐색 끝나면 worker가 최대 받을 수 있는 값을 추가 한다.
            result += maxValue

        return result

 

Java

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int result = 0; // 결과 반환할 변수
      try {
        int size = difficulty.length;
        // difficulty, profit 하나의 배열로 재 정의
        int[][] jobs = new int[size][2];
        for (int i = 0; i < size; i++) {
            jobs[i][0] = difficulty[i];
            jobs[i][1] = profit[i];
        }
        // difficulty 기준으로 정렬
        Arrays.sort(jobs, (a1, a2) -> a1[0] - a2[0]);

        size = profit.length;
        // worker  정렬
        Arrays.sort(worker);
        result = 0;
        int i = 0;
        int maxValue = 0; // 이전 profit보다 작을수 있어서 worker 들이 최대 받을수 있는 값을 저장 하기 위한 변수 이다.
        for(int work : worker){
            // two point
            // worker가 joibs 다 탐색 안하고 이전 탐색부터 시작해서 최대 할수 있는 난이도까지 간다.
           while(i < size && jobs[i][0] <= work){
               // 만약 이전 난이도 보다 profit이 적을 수 있어서 이전 profit이랑 비교해서 현재 difficulty까지 최대 값을 저장한다.
               maxValue = Math.max(maxValue, jobs[i][1]);
               i++;
           }
           // 최대 할수 있는 작업 탐색 끝나면 worker가 최대 받을 수 있는 값을 추가 한다.
           result += maxValue;
        }
      } catch (Exception e) {
        throw new RuntimeException(e);
      }

      return result;
    }
}