메리

투 포인터라는 알고리즘을 배웠음!

핵심 원리는 다음과 같음

1. start pointer / end pointer

2. end pointer을 오른쪽으로 옮기면 합이 증가

3. start pointer을 오른쪽으로 옮기면 합이 감소

4. pointer 이동한 뒤 목표합보다 작으면 -> end pointer를 오른쪽으로 옮긴다.

5. pointer 이동한 뒤 목표합보다 크면 -> start pointer를 오른쪽으로 옮긴다.

이제 여기서 문제마다

목표합과 같을때 무슨 액션을 할지 달라지는가 보다.

두번째 문제풀이

import java.util.*;

public class Problem1806 {
    //부분합
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numsCount = sc.nextInt();
        int targetSum = sc.nextInt();
        sc.nextLine();
        int[] nums = new int[numsCount];
        for(int i=0; i<numsCount; i++){
            nums[i] = sc.nextInt();
        }

        int end = 0;
        int start = 0;
        int sum = 0;
        int minLen = numsCount+1;
        //end 포인터를 오른쪽으로 옮기면 합이 증가
        //start 포인터를 오른쪽으로 옮기면 합이 감소
    
        while(end < numsCount){ //end 포인터가 배열 마지막부분까지 가도록
            if(sum < targetSum){ //합이 목표합보다 작은 경우 : end 포인터를 오른쪽으로 옮긴다.
                sum += nums[end++];
            }
            while(sum >= targetSum){//합이 목표합보다 크거나 같은 경우 : start 포인터를 오른쪽으로 옮긴다.
                sum -= nums[start++];
                minLen = Math.min(minLen, end-start+1);
            }
        }
        
        if(minLen == numsCount + 1){
            System.out.println(0);
        }else{
            System.out.println(minLen);
        }
    }
    
}

첫번째 문제풀이

import java.util.*;

public class Problem1806 {
    //부분합
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numsCount = sc.nextInt();
        int targetSum = sc.nextInt();
        sc.nextLine();
        int[] nums = new int[numsCount];
        for(int i=0; i<numsCount; i++){
            nums[i] = sc.nextInt();
        }

        int start = 0;
        int sum = 0;
        int minLen = numsCount+1;
        for(int end=0; end<numsCount; end++){
            sum += nums[end]; //end에 있는 수 더하기

            while(sum >= targetSum){//목표합보다 같거나 큰 경우 길이를 기록, start을 오른쪽으로 땡김
                minLen = Math.min(end-start+1,minLen);
                sum -= nums[start++];      
            } 

        }
        minLen = minLen == numsCount+1 ? 0 : minLen;
        System.out.println(minLen);
    }
    
}

아래코드는 다음과 같이 바꿀 수 있음

start += 1; 
sum -= nums[start-1];

=> sum -= nums[start++];