[Java] 투포인터 (백트래킹보다 효율적, 백준 2003번)

 

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

2003번: 수들의 합 2

 

1)  int Start Point, End Point 두 개의 포인터를 배열[0]에 두기

 

2)  S 포인터 ~ E 포인터 합 sum과 목표 숫자 M을 비교하기

 

3-1) 포인터를 증가시킬 때 

Start  포인터는 현재 위치의 원소를 sum에서 제거

End 포인터는 현재 위치의 원소를 sum에서 증가

 

# sum이 M보다 크다.

sum이 더 크니까 값을 줄여야 함. start 포인터를 1 증가시켜 현재 위치 원소 값을 sum에서 빼주기

 

# sum== M

cnt++;

같은 경우 후처리를 어떻게 해야하는지 블로그마다 달라 상당히 혼란스러웠는데, 다른 경우가 또 있나 찾아보아야 하기 때문에 end포인터를 1 증가시고 값을 sum에 더해줌

 

 

#  sum이 M보다 작다

sum이 더 작으니까 값을 늘려주어야 함. end 포인터를 1 증가시켜 end 인덱스의 값을 sum에 더해준다.

 

 * E 포인터가 끝 점에 도달했다면, start  포인터를 1 증가

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	 
	public static void main(String[] args) throws IOException  {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());	//수열 요소 개수
		int M = Integer.parseInt(st.nextToken());	//목표
		
		int[] arr = new int[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int start = 0, end = 0, sum = 0, cnt = 0;
		
		while(true) {
			if(sum>M) {
				sum-=arr[start++];
			} else if(end==N) {
				break;
			} else {
				sum+=arr[end++];
			}
			
			if(sum == M) 
				cnt++;
		}
		
		System.out.println(cnt);
	}
}

 

ref. 코딩 테스트 & 알고리즘 대회 핵심 노트 - 투 포인터(Two Pointers), 구간 합(Prefix Sum)

https://youtu.be/rI8NRQsAS_s