[인프런 자바/java] 3. 최대 매출 _디버깅의 눈물

 

체크 포인트

 

1. 투포인터(left lt, right rt)를 활용

 

예제)

10 3
12 15 11 20 25 10 20 19 13 15

 

-문제의 조건에 5<=N<=100,000라는 조건을 통해 단순히 모든 K일 간의 매출합을 구해서 비교한다면 메모리가 초과될 수 있음을 파악해야 한다.

-따라서 효율적인 메모리 사용을 위해 두 개의 점을 이동시키며 값을 구하는 투포인터를 활용했다.

-투포인터는 (1)두 점이 모두 같은 방향으로 움직이는 경우와 (2)한 방향으로 움직이는 경우가 있다. 이 문제에서는 왼쪽에서 오른쪽으로 (2)같은 방향의 투포인터를 사용했다. 

 

 

2.  먼저 처음 K일 간의 매출합 구하기

 

-K일 간의 매출합을 투포인터를 활용해 구하기 위해서는, 처음 K일 간의 합을 먼저 구해야 한다. 

-예제에서 3일 간의 매출합을 구하기 때문에, 처음 3일 매출의 합인 12+15+11=38을 구하면 투포인터 활용의 준비가 끝났다.

 

 

3. 새로운 K일 간의 매출합 = 기존 K일 간의 매출합 + 다음날의 매출 - 기존 K일 내에서 가장 오래된 날짜의 매출

-이후 3일 간 매출의 합을 연속해서 구할 때,

 

15+11+20=46, 11+20+25=56, ...

 

-위의 방식으로 구하면 메모리의 과용을 야기할 수 있다.

 

따라서

 

 

1)기존에 구한 K일 간의 매출합(12+15+11=38)에서

2)가장 오래된 날짜의 매출을 빼준 후(38-12=26),

3)다음날의 매출을 더해준다면(26+20=46),

 

 

새로운 K일 간의 매출합을 구할 수 있다!

 

 

            // 새로운 K일 간의 합 temp = 기존 K일 간의 합 temp + 하루 뒤 매출 - 하루 전 매출 
            
	    	       temp        =          temp      +   arr[rt] - arr[lt];

 

-이를 코드로 표현하자면 위와 같다. 

 

 

 

 

풀이

 

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

public  class Main {
	
	// 매출액을 담는 배열 변수 
	static int[] arr;
	// K일 간의 매출액 최대값 
	static int max;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	
    	// 전체 매출 일수 N
    	int N = Integer.parseInt(st.nextToken());
    	// K일 간 최대 매출액에 사용되는 변수 
    	int K = Integer.parseInt(st.nextToken());
    	
    	// 배열 초기화 
    	arr = new int[N];
    	
    	st = new StringTokenizer(br.readLine(), " ");
    	
    	// 배열 내 매출액 입력 
    	for(int i=0; i<N; i++){
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	// 탐색 시작 
    	solution(N,K);
    	
    } // end of main
    
    
    static void solution(int N, int K){
    	
    	// two pointers 활용을 위한 변수 left lt right rt
    	int lt = 0;
    	int rt = K;
    	// K일 간의 매출 합을 담아주는 임시 변수 temp 
    	int temp = 0;
    	
    	// 첫 K일 간의 매출 합 담기 
    	for(int i=0; i<K; i++){
    		temp += arr[i];
    	}
    	
    	// two pointers 탐색 시작 
	    while(rt<N){	    	
	    	// K일 간의 합이 현재까지 최대매출합보다 크다면,
	    	if(temp>max){
	    		//최대값 변경 
    		    max = temp;
	    	}
	    	
	    	// 새로운 K일 간의 합 temp = 기존 K일 간의 합 temp + 하루 뒤 매출 - 하루 전 매출 
	    	temp = temp + arr[rt] - arr[lt];
	    	
	    	// 포인터 증가 처리 
	    	rt++;
	    	lt++;
	    	
	    }
	    
	    // 투 포인터 탐색 후 최대값 출력 
	    System.out.println(max);
    }
    
} // end of Main