[Java] 투 포인터(Two Pointers), 구간 합(Prefix Sum)

(출처 - 동빈나 유튜브)

 

배열의 특정된 연속 구간을 처리하는 경우에 사용하는 투 포인터와 구간합 알고리즘에 대해 알아보려 한다.

• 수열에서 합이 N인 연속부분수열 → Two Pointer
• N개의 정수로 구성된 수열에서 M개의 쿼리에 해당하는 구간합 → Interval Sum

 

코테에서도 많이 나오는 것 같다.

 

특정한 합을 가지는 부분 연속 수열 찾기

[투 포인터를 활용한 알고리즘 설명]

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다.
2. 현재 부분 합이 M과 같다면, 카운트한다.
3. 현재 부분 합이 M보다 작거나 같다면, end를 1 증가시킨다.
4. 현재 부분 합이 M보다 크다면, start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

 

 

양의 정수일 때만 가능할 것 같다.

 

public class Main {
	
	public static void main(String[] args) {
		// 데이터의 개수 N과 부분연속 수열의 합 M을 입력받기
		int N = 5, M = 5;
		int[] data = {1,2,3,2,5};
		
		int result = 0;
		int summary = 0;
		int end = 0;
		
		// start를 차롇대로 증가시키며 반복
		for(int start = 0; start <N; start++) {
			// end를 가능한 만큼 이동시키기
			while(summary < M && end < N) {
				summary += data[end];
				end++;
			}
			// 부분합이 M일때 카운트 증가
			if(summary == M) {
				result++;
			}
			summary -= data[start];
		}
		
		System.out.println(result);
	}

}

 

 

구간 합 빠르게 계산하기

[문제 설명]

• 아래와 같이 N개의 정수로 구성된 수열이 있다.
• M개의 쿼리 정보가 주어진다.
  • 각 쿼리는 L과 R로 구성된다.
  • [L, R] 구간에 해당하는 데이터들의 합을 모두 구하는 문제
• 시간제한: O(N+M)

 

[Prefix Sum를 활용한 알고리즘 설명]

1. Prefix Sum을 계산하여 배열 P에 저장한다.
2. 매 M개의 쿼리 정보를 확인할 때, 구간 합은 P[R] - P[L-1]이다.

누적합 방식

1) L = 1, R = 3 → P[3] - P[0] = 60

2) L = 2, R = 5 → P[5] - P[1] = 140

...

이런 식으로

 

시간복잡도 : O(N+M)

 

public class Main {
	
	public static void main(String[] args) {
		// 데이터 개수 N과 데이터 입력받기
		int N = 5;
		int[] data = {10,20,30,40,50};
		
		// Prefix Sum 배열 계산
		int summary = 0;
		int[] prefix_sum = new int[5];
		for (int i = 0; i<N ;i ++) {
			summary += data[i];
			prefix_sum[i] = summary;
		}
		
		// 구간합 계산
		int left = 3;
		int right = 4;
		System.out.println(prefix_sum[right] - prefix_sum[left-1]);
		
	}
}