🔎 투포인터 알고리즘(Two Pointers Algorithm)

• 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태.

빨간색 포인터 : start / 파란색 포인터 : end 일 때

• 시작과 끝을 알 수 있도록 포인터 2개 존재.
• 맨 처음에는 start = 0 / end = 0 이며, 항상 start <= end 를 만족해야 한다.
• 두 개의 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할을 한다.

포인터를 이동하며 포인터 시작점부터 끝점까지의 "구간 합"을 구할 때 사용한다.

✏️ 활용 문제

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int S = sc.nextInt();
        int sum = 0;
        int[] nums = new int[N];
        int min = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;

        for (int i = 0; i < N; i++){
            nums[i] = sc.nextInt();
        }

        while (end <= N) {
            if (sum >= S) {
                min = Math.min(min, end - start);
                sum -= nums[start];
                start++;
                
            } else {
                if (end < N) {
                    sum += nums[end];
                    end++;
                } else {
                    break; // end가 N 이상으로 증가하는 것을 방지하기 위해 루프 종료
                }
            }
        }
        
        if (min == Integer.MAX_VALUE){
            System.out.println("0");
        } else {
            System.out.println(min);
        }
    }
}

N / S 입력 받기
합이 S 이상이 되는 구간의 길이 => 합 sum / 최솟값 min
투포인터 시작점 start / 종료점 end

① 크기가 N 인 배열 선언 후 N 만큼 반복하며 배열 채우기
② index 0 부터 start / end 시작 !
③ while 문으로 배열 경우의 수에 따라 if문 돌리기
④ min의 값이 처음 선언한 값과 같다면 ? min이 없는 것 ! => "0" 출력