문제 소개
배열 nums와 요청 배열 requests가 주어졌다고 가정해 보겠습니다. 각 요청은 requests[i] = [start_i, end_i] 형태로 표현되며, i번째 요청은 nums[start_i] + nums[start_i+1] + ... + nums[end_i]의 구간 합을 의미합니다. 우리가 구해야 할 것은 nums의 모든 순열 중에서 모든 요청의 총합이 최대가 되는 값입니다. 답이 매우 커질 수 있으므로 109+7로 나눈 나머지를 반환해야 합니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
nums = [10,20,30,40,50], requests = [[1,3],[0,1]]
배열을 [30,50,40,20,10]처럼 배치하면 다음과 같이 계산됩니다.
- requests[0]: nums[1] + nums[2] + nums[3] = 50 + 40 + 20 = 110
- requests[1]: nums[0] + nums[1] = 30 + 50 = 80
따라서 총합은 110 + 80 = 190이 되며, 이것이 만들 수 있는 최댓값입니다.
접근 방법: 스위프 라인 + 그리디
이 문제의 핵심은 각 인덱스가 몇 개의 요청 구간에 포함되는지(커버 횟수)를 파악하는 것입니다. 어떤 인덱스의 커버 횟수가 k라면, 그 위치에 값 x를 배치했을 때 총합에는 k × x만큼 기여합니다. 따라서 커버 횟수가 높은 인덱스일수록 큰 값을 배치하는 그리디 전략이 최적이 됩니다.
전체 알고리즘은 다음과 같이 진행됩니다.
- 각 요청 (s, e)에 대해 시작 이벤트 (s, 0)과 종료 이벤트 (e, 1)를 리스트 A에 추가합니다.
- A를 정렬한 뒤 스위프 라인 기법으로 커버 횟수를 추적합니다. 시작 이벤트를 만나면 cnt를 증가시키고, 종료 이벤트를 만나면 감소시킵니다.
- cnt가 변하지 않는 연속 구간은 동일한 커버 횟수를 가지므로, 이를 맵 fr에 '커버 횟수 → 인덱스 구간' 형태로 그룹화합니다.
- nums를 내림차순으로 정렬합니다.
- fr의 키(커버 횟수)를 내림차순으로 정렬한 뒤, 커버 횟수가 큰 그룹부터 nums의 큰 값들을 차례대로 할당하며 (구간 길이 × 커버 횟수)만큼 누적합니다.
- 매 단계마다 109+7로 나머지 연산을 적용하고, 최종 결과를 반환합니다.
예제 구현
이해를 돕기 위해 전체 구현 코드를 살펴보겠습니다.
from collections import defaultdict
def solve(nums, requests):
A = []
for s, e in requests:
A.append((s, 0))
A.append((e, 1))
A.sort()
fr = defaultdict(list)
cnt = 0
n = len(A)
i = 0
pre = 0
while i < n:
r = 1
while i < n - 1 and A[i+1] == A[i]:
r += 1
i += 1
p, flag = A[i]
if flag == 0:
cnt += r
if cnt - r > 0:
fr[cnt-r].append((pre, p-1))
pre = p
elif flag == 1:
cnt -= r
fr[cnt+r].append((pre, p))
pre = p+1
i += 1
nums.sort(reverse=True)
ks = list(fr.keys())
ks.sort(reverse=True)
ans = 0
m = 10**9 + 7
i = 0
for k in ks:
for s, e in fr[k]:
d = e - s + 1
ans += sum(nums[i:i+d]) * k
ans %= m
i += d
return ans
nums = [10,20,30,40,50]
requests = [[1,3],[0,1]]
print(solve(nums, requests))
입력
[10,20,30,40,50],[[1,3],[0,1]]
출력
190
복잡도 분석
이벤트 정렬과 nums 정렬이 전체 수행 시간을 지배하므로 시간 복잡도는 O((n + q) log(n + q))입니다. 여기서 n은 배열의 길이, q는 요청의 개수입니다. 공간 복잡도는 이벤트 리스트와 그룹 맵을 저장하는 데 필요한 O(n + q)입니다.