코딩테스트 연습 - 제곱 개수 배열

문제 설명

1이상의 정수로 이루어진 길이가 N인 1차원 정수 배열 arr가 주어집니다. 다음 규칙에 따라 배열 brr를 만듭니다.

배열 arr의 인덱스 순서대로 arr[i]를 배열 brr에 연속으로 arr[i]개씩 추가합니다.

예를 들어, arr가 [2, 1, 5]이면 brr는 [2, 2, 1, 5, 5, 5, 5, 5]입니다.

brr의 부분 배열¹ 구간의 양 끝을 나타내는 l, r이 주어질 때 아래 2가지를 구하려고 합니다.

K = brr의 l번째 원소부터 r번째 원소까지의 합 = brr[l-1] + brr[l] + brr[l+1] + ... + brr[r-2] + brr[r-1]
C = 길이가 r - l + 1인 brr의 부분 배열 중 합이 K인 부분 배열의 개수

1차원 정수 배열 arr와 구간의 양 끝을 나타내는 정수 l, r이 매개변수로 주어집니다. 이때, 1차원 정수 배열 [K, C]를 return 하도록 solution 함수를 완성해 주세요.

제한사항

1 ≤ arr의 길이 = N ≤ 100,000
- 1 ≤ arr[i] ≤ 100,000
- brr의 모든 원소의 합 ≤ 10¹⁵
1 ≤ l ≤ r ≤ arr의 모든 원소의 합
- l번째 원소부터 r번째 원소까지의 합을 구해야 합니다.

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹은 하나 이상의 하위 그룹으로 이루어져 있으며, 하위 그룹의 모든 테스트 케이스를 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

그룹	총점	테스트 케이스 그룹 설명
#1	5%	`l = r`
#2	15%	`N` ≤ 100, `arr[i]` ≤ 10
#3	35%	정답이 `C = 1`인 테스트 케이스만 주어집니다.
#4	45%	추가 제한 사항 없음

입출력 예

arr	l	r	result
[3, 2, 3, 1, 1]	5	7	[8, 2]
[2, 2, 2]	2	2	[2, 6]
[8, 8, 6, 5, 2, 9, 8, 4, 3, 10]	25	27	[15, 3]
[70195, 25471, 7389, 58187, 18454, 90532, 97667, 17148, 91636, 2810]	126058	462933	[27554327568, 1]
[16952, 70276, 16771, 37992, 87549, 54906, 36718, 20478, 57088, 27916, 51509, 83422, 51707, 18807, 80859, 2673, 37734, 93380]	149845	228204	[6860339640, 9190]
[49134, 86806, 94548, 88849, 95022, 28334, 16637, 79487, 23773, 7314, 47370, 50269, 36573, 9415, 44674, 28096]	61242	88535	[2369282964, 59513]

입출력 예 설명

입출력 예 #1

brr는 [3, 3, 3, 2, 2, 3, 3, 3, 1, 1]입니다. 5~7번째 원소로 이루어진 부분 배열의 합은 8(=K)입니다.
[3, 3, 3, 2, 2, 3, 3, 3, 1, 1] 또한 부분 배열의 합이 8이며 길이가 3입니다.
위 두 경우 외에는 합이 8이고 길이가 3인 부분 배열은 존재하지 않습니다.
[3, 3, 3, 2, 2, 3, 3, 3, 1, 1]은 부분 배열의 합이 8이지만 길이가 4이므로 C로 세지 않습니다.

따라서 [8, 2]를 return 해야 합니다.

입출력 예 #2

brr는 [2, 2, 2, 2, 2, 2]입니다. 2~2번째 원소로 이루어진 부분 배열의 합은 2(=K)입니다. 합이 2이고 길이가 1인 부분 배열의 개수는 6개입니다.

따라서 [2, 6]을 return 해야 합니다.

입출력 예 #3

[15, 3]을 return 해야 합니다.

입출력 예 #4

[27554327568, 1]을 return 해야 합니다.

입출력 예 #5

[6860339640, 9190]을 return 해야 합니다.

입출력 예 #6

[2369282964, 59513]을 return 해야 합니다.