연속 부분 수열

문제. N개의 수로 이루어진 수열이 주어지고 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하시오.

 

입력예시 

8 6
1 2 1 3 1 1 1 2

 

답 : 3

 

나의 답변 

import java.util.Scanner;

public class Main {	
	public int solution(int n, int m, int[] arr){
		int answer = 0, start=0, sum=0; 
		for( int i=0; i<n; i++ ) {
			sum+=arr[i]; 
			if(sum==m) {
				answer++;	
				i=start++; 
				sum=0; 
			}
			else if( sum > m ) {
				i=start++; 
				sum=0; 
			}
		}
		return answer;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] arr = new int[n]; 
		for( int i=0; i<n; i++ ) {
			arr[i] = sc.nextInt();
		}
		System.out.println(T.solution(n, m, arr));
	}
}

 

 

정답이나 현재 코드는 불필요한 반복문과 변수 사용으로 인해 효율성이 떨어진다. 

• 불필요한 중복을 줄이고 배열의 길이에 대한 조건은 for문으로 특정 조건에는 while문을 쓰는것으로 변경했다.
• 슬라이딩 윈도우 기법을 사용해 시간복잡도 O(N)을 유지한다. 
• for문과 while문이 함께 사용되고 있지만, 각각의 루프가 독립적으로 동작하는 것이 아니라, rt 포인터가 증가할 때마다 while 루프가 최대 한 번 실행되는 구조이다. 때문에 시간 복잡도는 O(N)이 된다.

슬라이딩 윈도우 더 알아보기

 

정정 답변

import java.util.Scanner;

public class Main {	
	public int solution(int n, int m, int[] arr){
		int answer = 0, sum=0; 
		int lt=0; 
		for( int rt=0; rt<n; rt++) {
			sum+=arr[rt]; 
			while(sum > m) {
				sum-=arr[lt++]; 
			}	
			if( sum==m ) answer++;
		}
		return answer;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] arr = new int[n]; 
		for( int i=0; i<n; i++ ) {
			arr[i] = sc.nextInt();
		}
		System.out.println(T.solution(n, m, arr));
	}
}