leeso

스터디할 때마다 자주 보는 문제인데, 정리를 해두지 않아서 자꾸 검색해보는게 번거로워서 아예 내 블로그에 기록해서 꺼내보고자 한다.

투포인터 알고리즘

1차원 배열에서 두 개의 포인터를 조작해서 원하는 결과를 얻는 알고리즘

장점 : 두 개의 포인터를 사용해서 기존의 방식보다 시간을 개선할 수 있다.

백준의 문제를 대표 예시로 활용하겠다.

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

문제 :

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

예제 입력 :

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

3

위의 예시를 확인해보면 10개의 자연수 중에서 부분합이 5가 되는 경우의 수를 구해야한다.

start, end라는 두 개의 포인터를 활용하여 풀어본다.

start : 부분 배열의 시작이 되는 인덱스

end : 부분 배열의 끝이 되는 인덱스

항상 성립해야하는 조건 : 포인터는 0에서 시작, start<=end

이후,

부분합 배열의 합과 구해야하는 값을 비교하여 포인터를 이동한다.

• 부분합 배열의 합 < 구해야되는 값

        end를 오른쪽으로 이동해서 부분합 배열의 크기를 증가시킨다.

• 부분합 배열의 합 >= 구해야되는 값

        start를 오른쪽으로 이동해서 부분합 배열의 크기를 감소시킨다.

JAVA로 구현한 코드

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

public class boj2003 {

    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[] numbers = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }
        
        int start = 0;
        int end = 0;
        int sum = 0;
        int answer = 0;

        while (end<=N) {
            if (sum < M) {
                sum = sum + numbers[end];
                end++;
            } else if (sum >=M) {
                sum = sum - numbers[start];
                start++;
            }
            if (sum == M)
                answer++;
        }
        System.out.println(answer);

    }
}