문제 링크와 소스코드

문제 파악

문제가 요구하는 것은 A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하기 이다.

시간복잡도 구하기

1) subA, subB 만들기 (누적합)

A 배열으로부터 subA 배열을 만든다.
B 배열으로부터 subB 배열을 만든다.

subA는 A의 부배열의 합을 요소로 가지는 배열이다. (subB도 마찬가지)
무슨 말이냐면
A = {1, 3, 1, 2} 이라면, 부배열은 {1}, {1,3}, {1,3,1}, {1,3,1,2}, {3}, {3,1}, {3,1,2}, {1}, {1,2}, {2}를 말한다. 즉 부분 집합을 말한다.

subA는 {1, 4, 5, 7, 3, 4, 6, 1, 3, 2}로 각 부 배열의 합을 요소로 가진다.

subA와subB는 누적합으로 만든다.
List<Long>으로 만드는 방법1과 Long[] 으로 만드는 방법2가 있다.

방법1

List<Long> subA = new ArrayList<>();
List<Long> subB = new ArrayList<>();

for (int i = 0; i < N; i++) {
	long sum = inputA[i];
	subA.add(sum);
	for (int j = i + 1; j < N; j++) {
		sum += inputA[j];
		subA.add(sum);
	}
}

for (int i = 0; i < M; i++) {
	long sum = inputB[i];
	subB.add(sum);
	for (int j = i + 1; j < M; j++) {
		sum += inputB[j];
		subB.add(sum);
	}
}

방법2

Long[] subA = new Long[(N * (N + 1)) / 2]; // N은 inputA의 길이
Long[] subB = new Long[(M * (M + 1)) / 2]; // M은 inputB의 길이

// P1 = subA
int count = 0;
for (int i = 0; i < N; i++) {
	long sum = inputA[i];
	for (int j = i; j < N; j++) {
		if (i == j) {
			subA[count++] = sum;
		} else {
			sum += inputA[j];
			subA[count] = sum;
			if (count < subA.length - 1) {
				count++;
			}
		}
	}
}

// P2 = subB
count = 0;
for (int i = 0; i < M; i++) {
	long sum = inputB[i];
	for (int j = i; j < M; j++) {
		if (i == j) {
			subB[count++] = sum;
		} else {
			sum += inputB[j];
			subB[count] = sum;
			if (count < subB.length - 1) {
				count++;
			}
		}
	}
}

subA의 개수는 (N * (N + 1)) / 2
subB의 개수는 (M * (M + 1)) / 2
이는 부분 집합의 개수 구하기와 동일하다.

여기까지 시간복잡도는 O(N^2)이다.

---

2) subA와 subB 정렬 + 슬라이딩 윈도우

A의 부 배열의 합 + B의 부 배열의 합을 더한 값(-> sum)을 T와 비교해야 한다.
여기서 슬라이딩 윈도우를 쓴다.

슬라이딩 윈도우는 사용 시 조건이 있다.
정렬이 되어 있거나 양수만 있을 때 슬라이딩 윈도우를 사용할 수 있다.

슬라이딩 윈도우를 위해서 다음이 필요하다.

• subA, subB의 포인터
• 정렬된 subA, subB

subA의 포인터 = 0 & subA는 오름차순
subB의 포인터 = 0 & subB는 내림차순

while(true)문을 돌면서 subA 포인터가 위치한 값 + subB 포인터가 위치한 값(-> sum)을 T와 비교해서 다음 if-else 문으로 포인터값을 증가시켜준다.

if (sum > T) {
	ptB++; // sum의 값을 줄여야 한다. 내림차순으로 정렬되어있는 subB의 포인터 값을 증가한다.
} else if (sum < T) {
	ptA++; // sum의 값을 늘려야 한다. 오름차순으로 정렬되어있는 subB의 포인터 값을 증가한다.
} else { // sum == T
	/* 3에서 설명 */
}

정렬 - 여기서 subA의 길이만큼 정렬하기 때문에 O(N^2 log{N^2})
포인터 - O(N^2)
여기까지 시간복잡도는 O(N^2) + O(N^2 log{N^2})

3) subA와 subB의 동률 찾기

아까 넘어갔던 else 문을 여기서 설명한다.

subA와 subB에는 각각 중복된 값이 존재할 수 있다.
배열을 정렬했기 때문에, 중복된 값이 존재한다면 바로 다음 인덱스에서 찾을 수 있다.

// 포인터
int ptA = 0;
int ptB = 0;

long result = 0;
while (true) {
	long currentA = subA[ptA];
	long target = T - currentA;

	if (subB[ptB] > target) {
		ptB++;
	} else if (subB[ptB] < target) {
		ptA++;
	} else { // target == subB[ptB]
		long countA = 0;
		long countB = 0;

		while (ptA < subA.length && subA[ptA] == currentA) {
			ptA++;
			countA++;
		}

		while(ptB < subB.length && subB[ptB] == target) {
			ptB++;
			countB++;
		}

		result += countA * countB;
	}

	if (ptA == subA.length || ptB == subB.length) {
		break;
	}
}

while문을 돌면서 값이 똑같다면 포인터와 카운트 값을 증가시킨다. 포인터가 배열의 사이즈를 넘어서면 while문을 빠져나온다.

탐색 - O(N^2)
여기까지 시간복잡도는 O(N^2) + O(N^2 log{N^2})

---

문제 POINT

문제를 보면 알겠지만 주어진 숫자의 범위가 매우 크다(10억).

계산을 하다보면 int 범위인 21억을 넘어갈지도 모른다. long 타입으로 변수를 선언해주는 것이 매우매우매우 중요하다.