알고리즘107 :: 투포인트 - BOJ_수들의합2

선형 시간 알고리즘입니다.  

import java.util.*;
public class 수들의합2_2 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n+1];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        int left = 0;
        int right = 0;
        int sum = a[0];
        int ans = 0;
        while(left<=right && right<n) {
            if(sum<m) {
                ++right;
                sum+=a[right];
            }else if(sum>m) {
                sum-=a[left];
                left+=1;
                if(left>right && left<n) {
                    right = left;
                    sum = a[left];
                }
            }else if(sum==m) {
                ++right;
                sum+=a[right];
                ans+=1;
            }
        }
        System.out.println(ans);
    }
}

위 알고리즘에서 투 포인트를 정합니다. (left, right를 선정합니다.) 

찾고자 하는 M의 값과 sum의 값을 비교해서 투 포인트를 나누게 됩니다.

위와 같이 left, right로 나눠서 진행하게 됩니다. sum 값이 현재 우리가 찾고자 하는 m의 값보다 작다면 right 를 하나 증가시키고 a[right] 의 값을 더하게 됩니다. 반면에 sum이 m보다 크게 된다면 이 경우 a[left]값을 우선적으로 빼주고 left를 하나 증가시켜줍니다. 또한 이 경우 left 가 right 를 넘어가면 안되기 때문에 체크해주는 코드가 필요합니다. 마지막으로 sum과 m이 같은 경우 정답을 하나 늘리고 sum이 m보다 작은 경우의 로직을 똑같이 수행하게 됩니다. 

투포인트 알고리즘은 전체를 순회할때 O(n^2)만에 수행하는것을 O(n) 으로 줄여주는 알고리즘입니다. 많이 나오는 부분이라 한번 정리해봤습니다. ㅠ__ㅠ

배열을 선언할 때 N+1 만큼 선언해야 합니다. 프로세스를 진행하다 sum==m 일 조건일 때 right 가 한번 증가하고 다음 arr에서 sum을 더하게 될때 java.lang.ArrayIndexOutOfBoundsException 가 발생합니다.