[종만북] 다이어트 현황 파악 : 이동 평균 계산하기 - 슬라이딩 윈도우(Sliding Window) + 누적합(Prefix Sum) JAVA

passionfruit200 2024. 5. 15. 09:38

2024. 5. 15. 09:38

출처 : 종만북 - 4.2 선형 시간 알고리즘 다이어트 현황 파악 : 이동 평균 계산하기

코드설명

슬라이딩 윈도우(Sliding Window) + 투포인터(Two Pointer) + 누적합(Prefix Sum)을 활용할 수 있습니다.

문제에서 두가지 방식으로 M달 간의 이동평균을 계산할 수 있습니다.

상세 설명은 코드 부분에 작성했습니다.

테스트케이스

입력 N(N달간의 몸무게), M(M달간의 이동평균) 이 입력으로 주어집니다.

입려 예시 1

30 3
70.8 71.0 71.3 72.0 72.9 73.1 73.2 73.2 73.7 73.7 74.6 74.8 75.8 76.8 77.6 78.4 78.7 79.6 80.1 80.8 80.8 81.8 82.2 82.2 83.0 83.8 84.6 84.7 85.2 86.1

결과 예시 1

 0.00 0.00 71.03 71.43 72.07 72.67 73.07 73.17 73.37 73.53 74.00 74.37 75.07 75.80 76.73 77.60 78.23 78.90 79.47 80.17 80.57 81.13 81.60 82.07 82.47 83.00 83.80 84.37 84.83 85.33

입력 예시 2

10 1
70.8 71.6 72.0 72.5 72.5 72.8 73.2 73.9 74.3 75.1

결과 예시 2

 70.80 71.60 72.00 72.50 72.50 72.80 73.20 73.90 74.30 75.10

입력 예시 3

10 4
69.6 68.8 68.0 67.8 67.1 66.8 65.8 65.1 64.1 64.0

결과 예시 3

 0.00 0.00 0.00 68.55 67.93 67.43 66.88 66.20 65.45 64.75

코드

1. 비효율적인 코드입니다.

O( (N-M+1) * M ) = O ( N*M - M^2 + M)

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static double answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		double[] weightArr = new double[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			weightArr[i] = Double.parseDouble(st.nextToken());
		}	
		double[] average1 = movingAverage1(weightArr, M);
		for(double a : average1) {
			System.out.print(" "+a);
		}
		System.out.println();
	}
	
	public static double[] movingAverage1(double[] A, int M) {
		double[] res = new double[N];
		for(int i=M-1;i<N;i++) {
			for(int j=0; j<M;j++) {
				res[i] += A[i - j];
			}
			res[i] /= M;
		}
		return res;
	}
	
}

2. 투포인터를 활용하여 개선한 코드입니다. ( 가장 빠릅니다. )

시간복잡도는 O(N) 입니다. 선형시간입니다.

아래와 같이 함수를 작성하면, 만약 M = 3일경우에, 앞의 2가지 계산하고, 나머지 1개를 추가로 더한뒤, 다시 맨 앞 1가지를 빼줍니다.

이렇게 하면, 투포인터를 손쉽게 구현하는 구조입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static double answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		double[] weightArr = new double[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			weightArr[i] = Double.parseDouble(st.nextToken());
		}	
		ArrayList<Double> average2 = movingAverage2(weightArr, M);
		for(double avg : average2) {
			System.out.print(" "+String.format("%.2f", avg));
		}
		System.out.println();
	}
	
	public static ArrayList<Double> movingAverage2(double[] A, int M) {
		ArrayList<Double> res = new ArrayList<>();
		//부분합을 사용합니다.
		double partialSum = 0; 
		//[0,M-2] 구간의 합을 계산합니다.
		for(int i=0;i<M - 1;i++) {
			partialSum += A[i];
			res.add((double) 0);
		}
		
		for(int i=M - 1;i<N;i++) {
			partialSum += A[i];
			res.add(partialSum / M);
			partialSum -= A[i - M + 1];
		}
		return res;
	}
	
}

더 깔끔한 투포인터 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static double[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new double[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Double.parseDouble(st.nextToken());
		}
		
		
		double sum = 0;
		for(int i=0;i<M - 1;i++) {
			System.out.print( String.format("%.2f", (double) 0) +" ");
			sum += arr[i];
		}
		
		for(int i=M - 1; i< N; i++) {
			sum += arr[i];
			System.out.print( String.format("%.2f", sum / M) +" ");
			sum -= arr[i - (M - 1)];
		}
		
	}
	
}

3. 투포인터 보다 느린 누적합 코드입니다.

처음에 문제를 떠올렸을때는, 누적합을 사용해야겠다는 생각이 먼저 떠올랐었습니다.

하지만, O(N + (N - M) ) = O( 2*N - M ) 의 시간복잡도로써, 2번 투포인터 방식보다 느립니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static double answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		double[] weightArr = new double[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			weightArr[i] = Double.parseDouble(st.nextToken());
		}	
		ArrayList<Double> average2 = movingAverage2(weightArr, M);
//		for(double avg : average2) {
//			System.out.print(" "+String.format("%.2f", avg));
//		}
//		System.out.println();
	}
	
	public static ArrayList<Double> movingAverage2(double[] A, int M) {
		ArrayList<Double> res = new ArrayList<>();
		//부분합을 사용합니다.
		double[] prefixSum = new double[N + 1];
		for(int i=0;i<N;i++) {
			prefixSum[i + 1] += prefixSum[i] + A[i]; 
		}
		
		for(int i=0;i<M - 1;i++) {
			res.add((double)0);
		}
		
		double tempSum = 0;
		for(int i=M; i<N;i++) {
			tempSum = prefixSum[i] - prefixSum[i - M];
			res.add(tempSum / 3);
		}
		
		return res;
	}
	
}

깔끔한 누적합 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static double[] arr, prefixSum;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new double[N];
		prefixSum = new double[N+1];
		st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<N;i++) {
			arr[i] = Double.parseDouble(st.nextToken());
			prefixSum[i + 1] = prefixSum[i] + arr[i];
		}
		for(int i=0;i<M - 1;i++) {
			System.out.print(String.format("%.2f ", (double) 0));
		}
		for(int i=M;i<N;i++) {
			System.out.print( String.format("%.2f", (prefixSum[i] - prefixSum[i - M]) / M ) +" ");
		}
		
	}
	
	
}

'알고리즘 > 알고리즘 문제해결 전략' 카테고리의 다른 글

[종만북] 알러지가 심한 친구들 음식 메뉴 정하기 - 완전탐색(BruteForce) + 재귀호출(Recursion) JAVA (0)	2024.05.15
[종만북] 성형 전 사진 찾기 - 이진탐색(Binary Search) JAVA (0)	2024.05.15
[종만북] 신문기사의 오류 확인하기 ( 400m 달리기 ) - JAVA (0)	2024.05.12
[종만북] 격자 위에서 기존에 있던 점까지의 거리의 합을 최소화하는 위치 찾기 - JAVA (0)	2024.05.12
[종만북] 사탕 나눠주기 문제 - JAVA (0)	2024.05.09

passionfruit200