[Ch.03 - 투 포인터] 4. 연속 부분수열 ##

4. 연속 부분수열

연속 부분수열 N개에서 합이 자연수 M이 되는 경우 횟수 구하기

 

입력값

8 6

1 2 1 3 1 1 1 2

출력값

3

 

---

(1)

1. while (p1 < n) 

합계에 p1이 가리키는 값을 더한다.

2. while (p2 < n&&sum<=m) 

p2가 n보다 작고, 합계가 m보다 작거나 같을 경우 계속 반복해 p2가 가리키는 값을 합계에 넣는다.

3. if (sum == m) 

합계가 m이 되는 경우 결과값에 +1한다.

package twopointer.ch03;

import java.util.Scanner;

//연속 부분수열
class Twopointer04_1 {
	static int[] arr;

	public int solution(int n, int m) {
		int p1 = 0;
		int p2 = 1;
		int sum = 0;
		int answer = 0;

		while (p1 < n) {
			sum += arr[p1];
			while (p2 < n&&sum<=m) {
				sum += arr[p2];
				p2++;
				if (sum == m) {
					answer++;
				}
//				if (sum > m) {
//					break;
//				}
//				sum<=m조건 대신 사용 가능
			}
			sum = 0;
			p1++;
			p2 = p1 + 1;
		}
		return answer;

	}

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

	}

}

 

(2)

1. while문 사용하지 않고, for문 한번으로 구현

2. m보다 크면 초기화 시키고, 시작점을 +1

3. m이 되면, 시작점을 빼고 다음 값부터 추가

//특정 연속 부분수열의 합
import java.util.Scanner;

public class Main {
	public int solution(int[] arr , int m) {
		int answer=0;
		int tmp=0;
		int p1=0;
		for(int i=0;i<arr.length;i++) {
			tmp+=arr[i];
			if(tmp==m) {
				answer++;
				tmp-=arr[p1];
				p1++;
			}else if(tmp>m) {
				tmp=0;
				i=p1++;
			}
		}
		
		
		return answer;
	}
	public static void main(String[] args) {
		Main T =new Main();
		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.println(T.solution(arr,m));
		
	}

}

 

 

+) 세련된 풀이

1. for (int rt = 0; rt < n; rt++) {
 포인터2가 n까지 반복하면서 포인터2의 값을 합계에 저장

2. if (sum == m)

//합계에 저장하는데 포인터가 1증가할때마다, 합계와 원하는 값의 크기를 비교한다.
(1) 원하는 값일 경우 -> 결과에 +1

(2)아닌 경우 -> 맨 앞의 값부터 빼고, 포인터를 증가시키면서 추가

3.while (sum > m)

합계가 m보다 크면 계속 반복하면서, 합계에서 포인터1의 값을 빼고, 포인터1에 +1

포인터1은 항상 +1씩 커지고, 포인터2는 합계가 m보다 커지면 포인터1이 가리킨 순서대로, 하나씩 빼서 다음값을 더한다.

4. if (sum == m)
원하는 값이 되면, 결과에 +1

 

package twopointer.ch03;

import java.util.Scanner;

public class Twopointer04 {
	// 연속부분수열
	// 연속 부분수열 N개에서 합이 M이 되는 경우 횟수 구하기

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

		kb.close();
	}

	public int solution(int n, int m, int[] arr) {
		// 1.ds
		int answer = 0, sum = 0, lt = 0;
		// 결과, 합계, 포인터1

		// 2.for, while
		for (int rt = 0; rt < n; rt++) {
			// 포인터2가 n까지 반복
			sum += arr[rt];
			// 포인터2의 값을 합계에 저장
			
			//합계에 저장하는데 포인터가 1증가할때마다, 합계와 원하는 값의 크기를 비교한다.
			//(1) 원하는 값일 경우 (2)아닌경우 -> 맨 앞의 값부터 빼고, 포인터를 증가시키면서 추가
			
			if (sum == m)
				answer++;
			// 원하는 값이 되면, 결과에 +1
			while (sum > m) {
				// 합계가 m보다 크면 반복
				sum -= arr[lt++];
				// 합계에서 포인터1의 값을 빼고, 포인터1 +1
				if (sum == m)
					answer++;
				// 원하는 값이 되면, 결과에 +1
			}
		}
		return answer;
	}

}

 

 

package twopointer.ch03;

import java.util.Scanner;

public class Twopointer04_4 {
	public int solution(int n, int m, int[]arr) {
		int answer=0, sum=0, lt=0;
		
		//lt기준이 아니라 rt기준으로 for문 -> rt는 항상 증가하지만, lt는 특정 조건에서 뺴야하므로
		for(int rt=0;rt<n;rt++) {
			sum+=arr[rt];
			if(sum==m) {
				answer++;
			}
			//rt를 추가하면, m과 같은지 항상 확인 -> sum: lt부터 rt까지의 합
			
			//sum>m인 경우
			while(sum>m) {
				sum-=arr[lt++];
				//lt++ : 뺀 다음에 증가, ++lt : 증가한 후에 뺀다.
				//뺀 다음에 같은지 확인
				if(sum==m) {
					answer++;
				}
			}
			//1 1 1 1 5 같은 경우처럼, lt를 여러번 빼야되는 경우도 존재하므로, while문 사용
		}
		
		return answer;
	}
	public static void main(String[] args) {
		Twopointer04_4 T = new Twopointer04_4();
		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.println(T.solution(n,m,arr));
	}

}

 

 

1. 하나씩 추가하면서 원하는 수와 같은지 체크한다.

2. 원하는 수보다 크면, 작아질때까지 앞에서부터 자른다. [자를때마다 원하는 수와 같은지 확인]

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    System.out.println(solution(n,m,arr));
  }
  static int solution(int n, int m, int[]arr){
    int answer=0;
    int sum=0;
    int lt=0;

      for(int i=0;i<n;i++){
        sum+=arr[i];
        if(sum==m) answer++;
        while(sum>m){
          sum-=arr[lt];
          lt++;
          if(sum==m) answer++;
        } 
      }
    
    return answer;
  }
}

---

1. for-while문 이용

(1) 총합이 작으면 반복해서 추가

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    

    //target값보다 크지 않으면 계속 반복
    int answer=0;
    for(int i=0;i<n;i++){
      int tmp=arr[i];
      int rt=i+1;
      while(tmp<k && rt<n){
        tmp+=arr[rt];
        if(tmp==k) answer++;
        rt++;
      }
      
    }
    System.out.println(answer);
  }
}

 

(2) 총합이 크면 반복해서 빼기

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    

    //target값보다 크면 계속 반복
    int answer=0;
    int sum=0;
    int lt=0;
    for(int rt=0; rt<n; rt++){
      sum+=arr[rt];
      if(sum==k) answer++;
      while(sum>k) {
        sum-=arr[lt++];
        if(sum==k) answer++;
      }
    }
    
    System.out.println(answer);
  }
}

 

---

+) 03.02

import java.util.Scanner;
import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int[]arr =new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    Main main = new Main();
    System.out.println(main.solution(arr, m));
  }
  public int solution(int[] arr, int m){
    //m보다 작으면 더하고, 같으면 추가하고, 크면 맨앞 뺀다.
    int p=0;
    int result=0;
    int answer=0;
    for(int i=0;i<arr.length;i++){
      result+=arr[i];
      if(result==m) answer++;
      while(result>m){
        result-=arr[p++];
        if(result==m) answer++;
      }
    }
    return answer;
  }
}