문제
: 먼저 첫 번째 줄 입력으로 N값하고 K값이 주어진 후,
두 번째 줄 입력으로 N개의 500이하의 정수가 주어진다.
그러면 주어진 정수값들 중에서 연속된 K개의 정수값의 합의 최댓값을 구하라.
(실제 문제에서는 N일동안의 매출액이 주어지고 ,
이때 연속된 K일 동안의 매출액 합의 최대값을 구하는 것)
(5<=N<=100,000)
(2<=k<=N)
EX)
N=10이고 K=3이며, 10일동안의 매출액이
12 15 11 20 25 10 20 19 13 15 으로 주어지면,
연속된 3일동안의 매출액 합중 최댓값을 구해야 하고,
그 결과는 11+20+25=56 이 된다.
이 문제의 요구사항 또한 문제에 명확하게 주어진 편이다.
말 그대로 입력한 배열 element들 중 연속된 K개의 합의 최댓값을 구하는 것이다.
이렇게 요구사항이 명확한 반면 , 해결 로직은 단순하게 생각해서는 안되는 문제였다.
[해결로직]
가장 단순하게 생각할 수 있었던 방식은 일일이 연속된 K개의 element합을 구하고 , 그합의 최댓값을 구하는 방식이었다.
- 실제로 처음에는 이 방식으로 코드를 구현하였지만
- 결국 시간초과에 걸리고 말았다.
- 각각의 element를 시작점으로 해야 하는 바깥 for문이 필요하였고
- 그 안에서 K개의 element합을 구하는 안쪽 for문 까지 총 2중 for문이 필요하였는데
- 그에 비해 문제 조건상의 N값과 K값 그리고 element 값의 범위가 방대했기 때문에 -> 이를 2중 for문으로 해결하기에는 무리가 있었던 것 같다.
결국 2중 for문 보다 더 효율적인 방식을 생각해냈어야 했고,
나는 연속된 K개의 합을 구할 때 - 굳이 매번 새롭게 K번의 덧셈을 하지 않아도 됨 을 깨달았다.
왜냐하면 e1 + e2 + e3이 이번 차례의 합이라면 - 다음차례의 합은 e2 + e3 + e4가 되고 - 이를 구하기 위해서는 이전 합에서 e1을 제외하고 e4만 더해주면 되기 때문이다.
[슬라이딩 윈도우]
: 실제로 이렇게 배열이나 리스트에 대해 일정한 범위의 element의 값을 비교할 때, 일종의 고정된 범위(or 크기)의 window를 만들고,
그 window의 start값과 end값만을 조절하며
window내의 element 값을 다루는 알고리즘을
"슬라이딩 윈도우" 알고리즘 이라고 한다.
- 이를 우리의 문제에 적용하면
-> 일단 처음 0번 element부터 k-1번 element까지의 합은 sum에 저장한 후
-> k번 element부터 n-1번 element까지 loop을 돌면서 순차접근 하고
-> 이때 각 iteration마다 arr[i-k]번 element는 빼주고 && arr[i]번 element는 더해주기를 반복하면
-> 연속된 k개의 element의 합을 손쉽게 구할 수 있다.
=> 즉 결과적으로는 한번의 loop만으로 연속된 k개의 element합을 구할수 있게 된다.
=> 따라서 매 iteration을 돌면서 최댓값을 계속 유지해나가면 , 시간 초과 없이 문제를 해결할 수 있다.
이를 기반으로 구현한 코드는 아래와 같다.
import java.util.Scanner;
public class Main {
public static int solution(int[] arr, int N, int K){
//일단 먼저 0번 element부터 k-1번 element까지의 합을 max 값에 넣어 두고
int max = 0;
for(int i=0; i<K; i++){
max += arr[i];
}
int sum = max;
//다음 윈도우의 끝 element를 더하고 && 이전 윈도우의 처음 element를 뺴주는것을 반복
for(int i=K; i<N; i++){
sum -= arr[i-K];
sum += arr[i];
if(sum > max)
max = sum;
}
return max;
}
public static void main(String[] args) {
//0. Scanner 준비
Scanner sc = new Scanner(System.in);
//1. N,K 배열 원소를 입력
int N = sc.nextInt();
int K = sc.nextInt();
int[] arr = new int[N];
for(int i=0; i<N; i++){
arr[i] = sc.nextInt();
}
//2. 입력받은 값들을 인자로 넘겨 solution()을 호출하여 -> 최대 매출액을 반환
int result = solution(arr, N, K);
//3. 최대 매출액 출력
System.out.println(result);
}
}
[정리 사항]
: 이번 슬라이딩 윈도우 문제에서 느낀 것 처럼,
이 투포인터 알고리즘과 / 슬라이딩 윈도우 알고리즘은
언뜻 보면 이중 for문 즉 O(n^2) 으로 해결할 수 있을것 같은 문제들을
시간 초과에 당하지 않기 위해 단일 for문 즉 O(n) 시간복잡도로
해결하는 방법들 이라는 점을 기억하자!
