문제 이해

숫자 배열이 주어질 것이다.
부분합 중 합이 S가 되는 것 중 가장 짧은 것의 길이를 구하는 문제이다.

• 부분합 : 인접한 수끼리 더해서 만들 수 있는 합

---

문제 풀이

포인터 2개를 준비할 것이다.
왼쪽 포인터를 left, 오른쪽 포인터를 right이라고 지정하자.

left와 right은 index가 0인 곳에 처음에 위치해있다.
그리고 left와 right는 아래와 같은 방식으로 움직인다.

1. right : left ~ right의 부분합이 S미만이라면 오른쪽으로 한 칸 이동한다.

2. left : left ~ right 부분합이 S이상이라면 오른쪽으로 한 칸 이동한다.

이는 아래 조건 때문에 가능한 풀이이다

• 10000이하의 자연수로 이루어진 수열 : 덧셈의 성질에 의해 양수끼리 더하면 무조건 값이 커질 수 밖에 없다.
  즉 left가 한 칸 오른쪽으로 이동하면 더해지는 수 한 개가 줄어들기 때문에 부분합이 작아질 것이고, right가 한 칸 오른쪽으로 이동하면 더해지는 수가 한 개 많아지므로 부분합이 무조건 커질 것이다.

right - left를 통해 부분합의 길이를 쉽게 알 수 있으므로 문제의 해결에 활용할 수 있고, 불필요한 계산이 많이 줄어들 것이다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static long S;
	static int[] arr;

	static void two_pointer() {
		int left = 0;
		int right = 0;
		long sum = 0;
		int length = Integer.MAX_VALUE;
		
		while(right<N) {
            // 오른쪽 포인터(right)이 배열의 범위를 넘어설 때까지 진행함
			if(sum < S) {
                // 합이 S 미만. right 포인터 오른쪽 이동
				sum+=arr[right];
				right++;
			}
			else {
            // 합이 S 이상. left 포인터 오른쪽 이동 
            // 이전까지 부분합이 S였던 최소 길이와 비교하여 더 작은 것을 선택함
				length = Math.min(length, right- left);
				sum-=arr[left];
				left++;
			}
		}
		
		while(left<N) {
        /*
        중요한 부분
        이 문제에서 오른쪽 포인터가 가장 오른쪽까지 갔어도 
        왼쪽 포인터의 이동이 가능할 수 있다.
        
        예를 들어 부분합이 3 이상이여야 할 경우, 1 2 3 배열은 (2,3)도 가능하지만
        (3)도 가능하다
        
        즉, left를 1씩 증가시켜 구간의 부분합이 S 미만이 될 때까지 
        오른쪽 이동 시켜주어야 한다.
        */
			if(sum < S) {
				break;
			}

			length = Math.min(length, right- left);
			sum-=arr[left];
			left++;
		}
		
		
		if(length==Integer.MAX_VALUE) System.out.println(0);
		else System.out.println(length);
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		S = sc.nextLong();
		arr = new int[N];
		
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextInt();
		}
		
		two_pointer();
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2번째 줄 틀렸습니다 : right 포인터를 모두 이동시켰다 하더라도 left 포인터를 최대한 이동시켰어야 하는데, 그 부분을 코딩하지 않았다. two_pointer() 메서드 중 2번째 while문을 추가함으로써 해결했다.