자바 알고리즘 문제 풀이 Two pointers, Sliding window Q03_ 최대 매출

설명

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.

만약 N=10이고 10일 간의 매출 기록이 아래와 같습니다. 이때 K=3이면

12 1511 20 2510 20 19 13 15

연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.

여러분이 현수를 도와주세요.

입력

첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.

두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

출력

첫 줄에 최대 매출액을 출력합니다.

예시 입력1	예시 출력
10 3 12 15 11 20 25 10 20 19 13 15	56

 

코드

내가 입력한 코드

package twoPointers_SlidingWindow;

import java.util.Scanner;

public class Q03 {

	public int solution(int N, int K, int[] arr) {
		int answer = 0;
		
		for(int i = 0;i <= N-K;i++) {
			if(answer < arr[i]+arr[i+1]+arr[i+2]) {
				answer = arr[i]+arr[i+1]+arr[i+2];
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		Q03 T = new Q03();
		Scanner kb = new Scanner(System.in);
		
		int N = kb.nextInt();
		int K = kb.nextInt();
		int[] arr = new int[N];
		
		for(int i = 0;i < N;i++) {
			arr[i] = kb.nextInt();
		}
		
		System.out.println(T.solution(N,K,arr));
		
	}
}

---

해설 코드

import java.util.*;
class Main {	
	public int solution(int n, int k, int[] arr){
		int answer, sum=0;
		for(int i=0; i<k; i++) sum+=arr[i];
		answer=sum;
		for(int i=k; i<n; i++){
			sum+=(arr[i]-arr[i-k]);
			answer=Math.max(answer, sum);
		}
		return answer;
	}

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

 

 

풀이 및 정리 

먼저 오랜만에 알고리즘 문제를 풀어서 감이 안 왔지만 조금 생각하다 보니 이전에 풀었던 문제들보다는 쉬운 편에 속했던 것 같다.  일단은 내가 푼 코드는 콘솔에 찍으면 정답처리는 되지만 채점은 오답이다...

손으로 쓰면서 풀면 생각보다 쉬운 것 같다. 아래와 같이 배열이 있다고 할 때 계산을 일단 해보자!
12 / 15 / 11 / 20 / 25 / 10 / 20 / 19 / 13 / 15
12/15/11 = 38 , 15/11/20 = 46, 11/20/25 = 56...... 이런 식으로 진행했을 때 제일 큰 합을 구하면 된다.

숫자의 인덱스가 0,1,2,3,4,5,6,7,8,9 일 때 더해지는 순서가 0,1,2 / 1,2,3 / 2,3,4 순서대로 더해지고 있다.
그러면 12/15/11 값 38, 다음에는 12/15/11  46이다. 
12/15/11이 값은 12/15/11/20의 합에 12를 빼줘도 된다는 소리이다. 

그렇다면 sum 변수를 선언하고 인덱스가 0,1,2의 합을 먼저 넣어준다.
그리고 위에 적은 방식처럼 계산해주면 된다.
12+15+11 => 12+15+11+20-12 => 15+11+20+25 - 15 => 11+20+25+10-11..이 순서대로 비교하면 된다.

Math.max(arg1, arg2) => arg1, arg2 중 큰 값 반환!