[Two Pointer] 수 들의 합2

📌 문제

문제 링크 : https://www.acmicpc.net/problem/2003

문제 유형 : 투 포인터

문제 난이도 : 실버3

 

문제 요약

구간 합 M을 만족하는 배열의 구간이 몇 개나 있는가?
단 O(n)으로 풀어야 한다.

📌 문제 풀이

간단하게 생각해서는, O(n^2) 으로 풀 수 있다. for loop를 두번 돌려서, 만족하는 구간을 찾아주면 된다.

그러나 해당 문제는 O(n)으로 풀어야 한다.

해당 문제는 투포인터를 이용해서 시간 복잡도를 줄일 수 있다.

left 와 right으로 구간을 잡는다. 포인터의 이름대로 범위는 left <= right 이다.

sum의 값이 M보다 작으므로, right을 전진시켜 준다.

이 때, sum을 구할 때 이중 for loop로 구하는 게 아니라 단순히 arr[++right]의 값만 더해주면 된다.

이번엔 sum의 값이 크다. left를 증가시켜줘야 sum의 값이 준다.

이 때도 역시 for loop을 돌 필요 없이, sum에 arr[left++] 의 값을 줄여주면 된다.

sum의 값이 M과 같아졌다. 이 때, right을 증가시키면 당연히 M을 넘는 값만 나올 것이다. 현재의 left에서 더 이상 하는 것은 의미 없으므로, count를 1증가시켜주고 left를 증가시켜준다. 그리고 당연히, sum에 left의 값을 빼주는 것도 추가해줘야 한다.

위와 같이 계속 진행하다 보면 right이 left보다 먼저 빠져나오게 된다.

left부터 right까지의 값 중에 sum을 만족하는 값이 있을 수 있으므로, while loop를 한번 더 돌려주면서 만족하는 값이 있는 지 찾아준다.

 

코드는 아래와 같다.

📌 코드

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;



public class Main {

    static int N,M;
    static int[] arr;

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();
        arr = new int[N];
        int cnt=0;

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

        int left = 0;
        int right =0;
        int sum = 0;

        sum += arr[left];

        while(left < N && right <N){
            if(right==N-1) break;
            if(sum==M) {
                cnt++;
                sum -= arr[left++];
            }else if(sum < M){
                sum += arr[++right];
            }else { // sum > M
                sum -= arr[left++];
            }
        }
        while(left<N){
            if(sum==M){
                cnt++;
            }
            sum -= arr[left++];
        }

        System.out.println(cnt);
    }
}