투 포인터 알고리즘(백준 2003번)

투 포인터 알고리즘

배열을 탐색하기 위해, 두 개의 포인터를 사용하여 배열을 순회하는 알고리즘

문제에서 이중for문으로 구하면 O(n^2)의 시간복잡도를 투 포인터 알고리즘을 활용하면 O(n)의 시간 복잡도로 풀이가 가능하다.

 

 

https://www.acmicpc.net/problem/2003

수들의 합 2

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초	128 MB	51870	24979	17060	48.389%

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

 

예제 입력 1 

4 2
1 1 1 1

예제 출력 1

3

예제 입력 2

10 5
1 2 3 4 2 5 3 1 1 2

예제 출력 2

3

 

 

풀이

1. 투 포인터 기법으로 left와 right 값을 0부터 수열 배열끼리의 합을 m과 비교한다.

2. left~right번째의 값들의 합(sum)이 m보다 작으면, 합(sum)이 커져야 하므로(sum<m), right번째 값을 더해준 다음 right의 위치를 옮겨준다.(sum+= array[right++])

3. left~right번째의 값들의 합(sum)이 m보다 크거나 같을 경우 합(sum)이 큰 관계로, left번째 값을 빼준 다음 left의 위치를 옮겨준다.(sum-= array[left++])

4. 합 값이 제시한 M의 값과 같을 경우(sum==m) count를 늘려주면 된다.(count++)

5. 제시한 배열의 길이 n 의 값이 right의 값과 같을 경우 반복문 종료(right!=n)

코드

public class FullSearch5 {
	public static void main(String[] args) {
		int n = 4;
		int m = 2;
		int[] array = {1, 1, 1, 1};
		int n2 = 10;
		int m2 = 5;
		int[] array2 = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2};
		solution(n,m,array);
		solution(n2,m2,array2);
	}
	public static void solution(int n, int m, int[] array) {
		int left = 0;
		int right = 0;
		int sum = 0;
		int count = 0;
		while(right!=n) { //0~n
			System.out.println("left : "+left+", right : "+right);
			if(sum < m) {  
				sum += array[right++]; 
			}else {
				sum -= array[left++];  
			}
			System.out.println("sum : "+sum);
			if( sum == m) { 
				count++; 
				System.out.println("cnt : "+count);
			}
		}
		System.out.println(count);
	}
}