https://leetcode.com/problems/maximum-profit-in-job-scheduling/description/
작업의 시작 시간, 끝 시간, 이익이 주어질 때 적당히 골라서 최대의 이익을 얻는 문제이다.
문제에 주어진 힌트를 참고해서 접근했는데 두 번째 힌트인
Sort the elements by starting time, then define the dp[i] as the maximum profit taking elements from the suffix starting at i.
가 이해가 가지 않아서 GPT한테 물어보았다.
문제 풀이의 핵심
- 작업을 시작 시간 기준으로 정렬하는 것이 첫 번째 단계입니다. 왜냐하면 이 방법이 가장 직관적이고, 이후 동적 프로그래밍 접근법을 적용하기 쉬워지기 때문입니다.
- dp[i]는 i번째 작업부터 끝까지 고려할 때 최대 이익을 의미합니다. 즉, 이 작업을 선택하거나 선택하지 않을 수 있는 모든 경우를 고려하여, 얻을 수 있는 최대 이익을 계산하는 것입니다.
라는 설명과 함께 예시를 들어주어서 방향을 잡고 코드를 작성했다.
코드 1 - 실패
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
ans = 0
jobs = []
for i, s in enumerate(startTime):
jobs.append((s, endTime[i], profit[i]))
jobs.sort()
dp = [0] * len(profit)
dp[-1] = jobs[-1]
for i in range(len(profit)-2, -1, -1):
s, e, p = jobs[i]
next = i+1
compare = []
while next < len(dp) and e > dp[next][0]:
compare.append(dp[next])
next += 1
if next < len(jobs):
compare.append((s, dp[next][1], p + dp[next][2]))
else:
compare.append((s, e, p))
dp[i] = max(compare, key=lambda x: x[2])
return max(dp, key=lambda x: x[2])[2]작업을 시작시간으로 정렬하고, dp는 작업의 개수만큼 확보를 한 뒤에 dp[-1]에는 마지막 작업을 넣었다.
작업을 거꾸로 진행하면서 지금 작업과 겹치지 않는 다음 작업을 dp에서 찾아서 이익을 더하거나, 지금 작업과 겹치는 다음 작업과 이익을 비교해서 지금 작업의 dp를 업데이트 했다.
그리고 시간초과가 발생했는데 아무래도 지금 작업과 겹치지 않는 다음 작업을 찾는데서 시간초과가 발생한 것 같다.
hint3번에 이진탐색을 사용하라고 되어 있었는데 사용해야 할 때인 것 같다.
코드 2
class Solution:
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
ans = 0
jobs = []
for i, s in enumerate(startTime):
jobs.append((s, endTime[i], profit[i]))
jobs.sort()
print(jobs)
dp = [0] * len(profit)
dp[-1] = jobs[-1]
for i in range(len(profit)-2, -1, -1):
s, e, p = jobs[i]
start = i+1
end = len(dp)
while start < end:
mid = (start + end) // 2
if jobs[mid][0] >= e:
end = mid
else:
start = mid + 1
if start < len(dp):
dp[i] = max(dp[i+1], (s, dp[start][1], p + dp[start][2]), key=lambda x: x[2])
else:
dp[i] = max(dp[i+1], jobs[i], key=lambda x: x[2])
return max(dp, key=lambda x: x[2])[2]작업 시간을 기준으로 이진탐색을 진행했다. 계속 실패해서 GPT의 도움을 받아 수정을 거듭해서 겨우 통과한 코드이다.
jobs의 시간을 기준으로 현재 작업과 비교해서 가장 빨리 시작할 수 있는 다음 작업을 선택했다. 그리고 만약 유효한 작업이라면 이익을 더해주었고, 아니라면 그냥 dp의 다음 칸과 비교했다.
DP 점화식 세우기
DP 문제를 풀 때 점화식을 세우고 접근해야하는 데 그거를 간과했다. 점화식을 생각하지 않고 그냥 머리속에서 떠오르는 대로 풀다보니까 한참 헤맸던 것 같다. 그래서 첫 코드에서는 dp[i]부터 dp[-1]까지 전체를 보면서 max값을 찾았는데 굳이 그럴 필요가 없이 바로 다음 작업과 비교하면 되는 문제였었다.
이진 트리 조건 잘 잡기
이진트리를 처음 만들었을 때도 계속 문제가 풀리지 않아서 헤맸다.
조건을 만족하는 최소값을 찾을 때는 start를 확인하고 조건을 만족하는 최대값을 찾을 때는 end를 확인하는 것을 기본으로 접근해야할 것 같다.
