투포인터(백준 2003번), 슬라이딩 윈도우(자바)

투포인터

: 부분 배열의 길이가 가변적일 때

배열의 합이 m인 부분 배열을 구한다고 하면

1. L ~ R 까지 부분배열의 합이 M보다 크면 L + 1

2. L ~ R 까지 부분배열의 합이 M보다 작으면 R + 1

3. L ~ R 까지 부분배열의 합이 M이면 L + 1, result 값 += 1

 

2003번: 수들의 합 2 (acmicpc.net)

2003번: 수들의 합 2

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int left = 0;
        int right = 0;
        int cnt = 0;
        int sum = 0;
        while (true) {
            if (sum >= m) {
                sum -= arr[left++];
            }
            else if (right >= n) break; //right++을 수행하는 문장이 있으므로 그 전에 right >= n인지 확인한다
            else sum += arr[right++];  //처음에 sum이 0이므로 이 문장을 수행하게 되기 때문에 
                                     ++right이 아니라 right++을 수행하여 arr[0]이 sum에 더해지도록 한다
            if (sum == m) cnt++;  //sum에 대해 조건에 따라 위의 연산을 마친 후 m과 같은지 비교한다
        }
        System.out.println(cnt);

    }
}

 

슬라이딩 윈도우

: 부분배열의 길이가 고정적일 때

길이가 고정이므로 포인터가 하나만 있어도 된다.

 

2559번: 수열 (acmicpc.net)

2559번: 수열

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        int sum = 0;
        int max = 0;
        int result = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (i == k-1) {
                max = sum;  //초기 max값
            }
            if (i >= k) {
                sum -= arr[i-k];  //한칸씩 뒤로 밀면서 sum 중 max 찾기
                max = Math.max(max, sum);
            }
        }
        System.out.println(max);

    }
}

 

 

참고

[알고리즘] 투 포인터, 슬라이딩 윈도우 알고리즘 자바 구현 (백준 2003, 2559) (tistory.com)

[알고리즘] 투 포인터, 슬라이딩 윈도우 알고리즘 자바 구현 (백준 2003, 2559)