문제 설명
크기가 같은 두 개의 리스트 deadlines와 credits가 있다고 가정해 보겠습니다. 이 두 리스트는 과제 정보를 나타내며, deadlines[i]는 i번째 과제의 마감일(일 단위), credits[i]는 해당 과제를 완료했을 때 받을 수 있는 학점을 의미합니다.
하나의 과제를 완료하는 데는 하루가 걸리며, 마감일 당일 또는 그 이전까지 완료해야 합니다. 또한 동시에 여러 과제를 수행할 수는 없습니다. 이때, 일부 과제를 골라 완료함으로써 얻을 수 있는 최대 학점의 합을 구하는 것이 목표입니다.
입력 예시
deadlines = [1, 2, 2, 2]
credits = [4, 5, 6, 7]
이 경우 출력은 18이 됩니다. 학점이 5인 과제를 0일째에, 학점이 6인 과제를 1일째에, 학점이 7인 과제를 2일째에 완료하면 5 + 6 + 7 = 18학점을 얻을 수 있기 때문입니다.
풀이 방법
이 문제는 그리디(Greedy) 알고리즘으로 효과적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 학점이 높은 과제부터 우선적으로 처리한다.
- 각 과제에 대해 마감일부터 거꾸로 탐색하면서 아직 비어 있는 날짜 슬롯을 찾아 배치한다.
- 배치에 성공하면 해당 과제를 완료한 것으로 간주하고 학점을 누적한다.
구체적인 절차를 단계별로 살펴보면 다음과 같습니다.
- (마감일, 학점) 쌍을 만들고, 학점을 기준으로 내림차순 정렬합니다.
- 정렬된 리스트가 비어 있다면 0을 반환합니다.
- 크기가 (최대 마감일 + 1)이고 0으로 초기화된 배열
res를 만듭니다.res[k]는 k번째 날이 이미 사용되었는지를 나타냅니다. - 정답을 저장할 변수
ans를 0으로 초기화합니다. - 정렬된 각 쌍 (i, j)에 대해, k를 i부터 0까지 감소시키며 확인합니다.
res[k]가 0이라면(그날이 비어 있다면),res[k]를 1로 표시하고ans에 학점 j를 더한 뒤 내부 반복을 종료합니다.- 모든 과제를 확인한 후
ans를 반환합니다.
파이썬 구현 코드
class Solution:
def solve(self, deadlines, credits):
a = sorted(list(zip(deadlines, credits)), key=lambda x: x[1], reverse=True)
if not a:
return 0
res = [0] * (max(deadlines) + 1)
ans = 0
for i, j in a:
for k in range(i, -1, -1):
if not res[k]:
res[k] = 1
ans += j
break
return ans
ob = Solution()
deadlines = [1, 2, 2, 2]
credits = [4, 5, 6, 7]
print(ob.solve(deadlines, credits))
실행 결과
입력
[1, 2, 2, 2], [4, 5, 6, 7]
출력
18
복잡도 및 추가 팁
시간 복잡도는 정렬에 O(n log n)이 소요되고, 각 과제마다 최대 마감일만큼 슬롯을 탐색하므로 전체적으로 O(n × d)입니다(여기서 d는 최대 마감일). 공간 복잡도는 O(d)입니다.
입력 크기가 매우 큰 경우에는 우선순위 큐(힙)를 활용하거나, 유니온-파인드(Union-Find) 자료구조로 각 날짜에서 가장 가까운 빈 슬롯을 빠르게 찾는 방식으로 성능을 더욱 개선할 수 있습니다.