99클럽 코테 스터디 29일차 TIL + Maximum Profit in Job Scheduling (DP, 이진 탐색)

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제 & 키워드

• LeetCode - Maximum Profit in Job Scheduling (문제 링크)
• 동적 프로그래밍 (Dynamic Programming)
• 이진 탐색 (Binary Search)

 

---

 

문제 설명

주어진 n개의 작업이 있습니다. 각 작업은 시작 시간 startTime[i], 종료 시간 endTime[i], 그리고 이익 profit[i]을 가지고 있습니다. 이 작업들을 최대한 겹치지 않게 선택하여 얻을 수 있는 최대 이익을 구하는 문제입니다.

주어진 작업은 겹칠 수 없으며, 작업이 끝나는 시간에 다른 작업을 시작할 수 있습니다. 이때, 최대 이익을 구하는 문제를 해결해야 합니다.

입력

• startTime, endTime, profit의 길이는 모두 같으며, 최대 50,000개까지 주어집니다.
• 각 시간 값은 1 이상 1,000,000,000 이하이며, 각 이익 값은 1 이상 10,000 이하입니다.

출력

• 겹치지 않는 작업들을 선택했을 때의 최대 이익을 반환합니다.

입출력 예시

예제 1

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: 첫 번째와 네 번째 작업을 선택하여 최대 이익 120을 얻을 수 있습니다.

예제 2

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: 첫 번째, 네 번째, 다섯 번째 작업을 선택하여 최대 이익 150을 얻을 수 있습니다.

예제 3

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

 

---

 

문제 접근

이 문제는 동적 프로그래밍(DP)과 이진 탐색을 결합하여 해결할 수 있습니다. 주어진 작업들을 종료 시간을 기준으로 정렬한 후, 각 작업에 대해 이전 작업들과 겹치지 않는 최대 이익을 계산하여 최종적으로 최대 이익을 구하는 방식입니다.

1. 작업 정렬
   • 먼저, 작업을 종료 시간을 기준으로 정렬합니다.
   • 작업을 순차적으로 고려할 때, 이전 작업들 중 현재 작업과 겹치지 않는 최대 이익을 효율적으로 계산할 수 있습니다.
2. 이진 탐색 활용
   • 각 작업을 고려할 때, 현재 작업과 겹치지 않는 가장 최근의 작업을 찾기 위해 이진 탐색을 사용합니다.
3. DP 배열 작성
   • DP 배열을 사용하여 각 작업까지의 최대 이익을 기록합니다.
   • 배열을 갱신하면서 최종적으로 최대 이익을 구합니다.

 

풀이 - Java 코드

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    private static class Job {
        private int start;
        private int end;
        private int profit;
        Job(int start, int end, int profit) {
            this.start = start;
            this.end = end;
            this.profit = profit;
        }
    }

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Job[] jobs = new Job[n];

        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }

        // 종료 시간을 기준으로 정렬
        Arrays.sort(jobs,(Comparator.comparingInt(o -> o.end)));

        int[] dp = new int[n];

        dp[0] = jobs[0].profit;

        for (int i = 1; i < n; i++) {
            int includeProfit = jobs[i].profit;

            // 이진 탐색으로 겹치지 않는 이전 작업 찾기
            int l = binarySearch(jobs, i);

            if (l != -1) {
                includeProfit += dp[l];
            }

            // 현재 작업을 포함하는 경우와 포함하지 않는 경우 중 최대 이익 선택
            dp[i] = Math.max(dp[i - 1], includeProfit);
        }

        return dp[n - 1];
    }

    // 이진 탐색으로 현재 작업과 겹치지 않는 마지막 작업의 인덱스 찾기
    private int binarySearch(Job[] jobs, int index) {
        int low = 0, high = index - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (jobs[mid].end <= jobs[index].start) {
                if (jobs[mid + 1].end <= jobs[index].start) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }
}

풀이 설명

1. 작업 클래스 생성
   • Job 클래스를 생성하여 각 작업의 시작 시간, 종료 시간, 이익을 저장합니다.
2. 정렬
   • 주어진 작업들을 종료 시간을 기준으로 오름차순으로 정렬합니다.
   • 작업들을 순차적으로 고려할 때, 이전 작업들과의 겹치는여부를 효율적으로 판단하기 위함입니다.
3. DP 배열 초기화
   • 첫 번째 작업의 이익으로 DP 배열을 초기화합니다.
   • 각 작업을 고려하여 최대 이익을 갱신합니다.
4. 이진 탐색
   • 현재 작업과 겹치지 않는 이전 작업을 찾기 위해 이진 탐색을 사용합니다. 이 탐색 결과를 활용하여 DP 배열을 갱신합니다.
5. 최종 출력
   • 마지막 작업까지의 최대 이익을 반환합니다.

 

---

 

마무리하며

• 이 문제는 동적 프로그래밍과 이진 탐색의 결합을 통해 효율적으로 최대 이익을 계산할 수 있음을 보여줍니다.
• 겹치지 않는 작업을 선택하여 최대 이익을 구하는 문제에서 이진 탐색을 활용하여 문제를 해결했습니다.