투 포인터

1. 투 포인터

포인터를 2개 사용하여 더 빠르게 배열을 탐색할 수 있다.

 

2. 예시문제

www.acmicpc.net/problem/2559

2559번: 수열

3. 설명

문제의 N의 크기가 100000이기 때문에 이중for문을 쓰면 시간 초과가 난다.

 

그렇기 때문에 투 포인터를 사용해야한다.

 

k개를 탐색한 경우 가장 마지막에 더한 값을 빼주고, 현재 값을 더하는 식으로 해결 가능

import java.util.Scanner;

public class back_2559수열 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int cnt = 0;//현재 선택한 갯수
		int sum = 0;
		int ans = -Integer.MAX_VALUE;
		int arr[] = new int[100000];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			if(cnt<k) {
				cnt++;
				sum+=arr[i];
				if(cnt==k) {
					ans = ans < sum ? sum : ans;
				}
			}else {
				if((sum>0 && arr[i-k]<0) || sum<0 && arr[i-k]<0)
					sum+=Math.abs(arr[i-k]);
				else
					sum-=arr[i-k];
				sum+=arr[i];
				ans = ans < sum ? sum : ans;
			}
		}
		System.out.println(ans);
	}
}

 

가장 마지막에 더한 값이 음수라면 sum에 더해야 한다

if((sum>0 && arr[i-k]<0) || sum<0 && arr[i-k]<0)
		sum+=Math.abs(arr[i-k]);

 

 

가장 마지막에 더한 값이 양수라면 sum에 그 값을 빼준다

sum-=arr[i-k];

 

현재 값을 더하고 최대값 갱신

sum+=arr[i];
ans = ans < sum ? sum : ans;