[알고리즘] Two pointers, Sliding window(4) : 연속 부분수열(JAVA)

👔 문제

👖 풀이

• 만약 2중 for문으로 풀게 된다면 시간복잡도는 O(N^2)이 된다.
• N의 범위는 1~100,000이기 때문에 O(N^2) 굉장히 큰 값이 설정된다.
• two pointer나 sliding window 알고리즘은 O(N^2)의 시간 복잡도를O(N)으로 바꿔 준다.

• sum 은 lt~rt까지의 합이다.
  lt~rt까지의 합을 sum에 저장하고 입력값 6과 같은지 확인한다.
  lt =0, rt =1일 때,
  1+2 = 3 != 6 이므로 rt++ 해준다.
  1+2+1 = 4 != 6 이므로 rt++ 해준다.
  1+2+1+3 = 7 != 6 인데 입력값 6보다 큰 수가 나온다.
  따라서 rt++을 처리해 주어도 성립이 불가능하다.

int answer = 0, sum = 0, lt = 0;
for(int rt = 0;rt<n;rt++){
	sum += arr[rt];
}

위의 코드는 sum값을 rt < n 일 때 까지, arr[0]+arr[1]+...+ 반복해서 더 해준다.

여기서 조건문을 추가해 sum == m 일때 answer++ 를 해주자.

int answer = 0, sum = 0, lt = 0;
for(int rt = 0;rt<n;rt++){
	sum += arr[rt];
    if(sum == m) answer++;
}

여기서 rt++를 해주고 있는데 sum >= m 이면, lt의 값을 sum에서 빼주고 lt++를 해준다.

while(sum>=m){
	sum -= arr[lt++];
    if(sum == m)
    	answer++;
}

🧦 소스코드

package algolecture;

import java.util.Scanner;

public class Main28 {
    public int solution(int n, int m, int[] arr){
        int answer = 0, sum =0, lt =0;
        for(int rt = 0; rt<n; rt++){
            sum += arr[rt];
            if(sum == m) answer++;
            while(sum>=m){
                sum-= arr[lt++];
                if(sum==m)
                    answer++;
            }
        }
            return answer;
    }


    public static void main(String[] args) {
        Main28 T = new Main28();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = kb.nextInt();
        }
        System.out.print(T.solution(n,m,arr));
    }
}