양의 정수로 이루어진 길이 n의 배열 nums가 있다고 가정해 보겠습니다. 이 배열의 모든 비어 있지 않은 연속된 하위 배열(부분 배열)의 합을 계산한 뒤, 이 값들을 오름차순으로 정렬하면 총 n*(n+1)/2개의 숫자로 이루어진 새로운 배열이 만들어집니다. 우리가 해야 할 일은 이 새로운 배열에서 인덱스 left부터 right까지(1부터 시작하는 인덱스, 양 끝 포함)에 해당하는 숫자들의 합을 구하는 것입니다.
결과값이 매우 커질 수 있으므로, 최종 답은 10^9 + 7로 나눈 나머지를 반환해야 합니다.
예시
예를 들어 입력이 nums = [1,5,2,6], left = 1, right = 5라고 해봅시다. 이 경우 모든 하위 배열의 합은 다음과 같습니다.
1, 5, 2, 6, 6, 7, 8, 8, 13, 14
이 값을 정렬하면 [1, 2, 5, 6, 6, 7, 8, 8, 13, 14]가 되고, 인덱스 1부터 5까지의 합은 1+2+5+6+6 = 20이므로 출력 결과는 20입니다.
해결 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- m := 10^9 + 7 (모듈로 상수)
- n := nums의 길이
- a := 새로운 빈 리스트 생성
- i를 0부터 n-1까지 반복:
- j를 i부터 n-1까지 반복:
- i와 j가 같으면 → a의 끝에 nums[j]를 추가
- 그렇지 않으면 → a의 끝에 ((nums[j] + a의 마지막 원소) mod m)을 추가
- j를 i부터 n-1까지 반복:
- 리스트 a를 오름차순으로 정렬
- sm := a[left-1:right] 범위의 모든 원소 합 계산
- sm mod m 반환
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(nums, left, right):
m = 10**9 + 7
n = len(nums)
a = []
for i in range(n):
for j in range(i, n):
if i == j:
a.append(nums[j])
else:
a.append((nums[j] + a[-1]) % m)
a.sort()
sm = sum(a[left-1:right])
return sm % m
nums = [1, 5, 2, 6]
left = 1
right = 5
print(solve(nums, left, right))입력
[1,5,2,6], 1, 5
출력
20
코드 설명
이 알고리즘은 이중 반복문을 사용해 시작 인덱스 i와 끝 인덱스 j를 조합하며 모든 연속 하위 배열의 합을 효율적으로 누적합니다. 이전까지의 합에 현재 원소를 더하는 방식을 사용하기 때문에 각 하위 배열의 합을 처음부터 다시 계산할 필요가 없습니다. 모든 합을 구한 뒤 정렬하고, 슬라이싱(left-1:right)을 통해 원하는 범위의 합만 추출하여 모듈로 연산 후 반환합니다.
시간 복잡도는 하위 배열 개수가 O(n²)이고 정렬에 O(n² log n²)이 소요되므로 전체적으로 O(n² log n) 수준입니다. n이 크지 않은 입력에서는 충분히 실용적인 접근 방식입니다.