드디어 누적합 단계로 들어왔다. 이번 문제는 누적 합을 이용하여 연속된 날짜간의 온도의 최대값을 구하는 문제이다.
각 날짜에 대한 온도와 구해야 하는 날짜를 받아서 계산을 해야하는데 누적합을 이용하여 계산 시간을 줄이는 것이 핵심인 문제였다.
그럼 어떻게 문제를 풀었는지 살펴보자.
반복의 반복...
이번 문제를 누적합을 쓰지 않고 계산한다고 생각해보자.
총 10일이 주어지고 구해야하는 날짜가 5일인 경우를 생각해보자.
계산은 위의 그림과 같이 이루어져야 한다.
중요한것은 위의 그림을 어떻게 구현할 것인가 인데, 단순히 반복문을 이용하여서 로직을 만든다고 생각해보자.
나와야하는 값은 총 6개이므로 반복도 6번이 될것이다.
그렇다면 전체 갯수 n개가 주어지므로 반복을 최소화 하기 위해 메서드를 통하여 만든다고 생각해보자.
로직은 다음과 같이 될 것이다.
public static int cal(int st, int end){
int sum = 0;
if(end > n) return 0;
for(int i = st; i < end; i++){
sum += arr[i];
}
return sum;
}전역 변수로 전체 갯수 n과 온도 배열 arr가 있다고 가정할때, 입력받은 종료값이 배열의 최대 갯수인 n보다 크다면 return 시키고 아니라면 해당 배열의 온도값을 모두 더하여 return 하는 메서드이다.
이렇게 하면 처음부터 끝까지 반복하지 않고 부분부분만 반복하여 값을 얻을 수 있을테니 반복횟수가 조금은 줄어들 것이지만, 결과적으로 6개의 값이 필요하므로 여러번 반복을 해야하는 문제 자체는 해결되지 않았다.
그렇다면 최소한의 반복을 하기 위해선 어떻게 해야할까?
누적합을 사용해보자!
누적합이란 문자 그대로 누적된 값을 사용하여 계산하는 알고리즘을 말한다.
예를 들어 이번 예제의 경우 각 온도의 갯수만큼 누적합을 저장하는 배열을 만들고 각 온도의 인덱스에 해당 인덱스 까지의 누적합을 담는다.
여기서 고려할 점은, 구해야 하는 날짜가 동적이라는 점이였는데 나는 이부분을 인덱스가 구해야 하는 날짜보다 크다면 해당 인덱스의 값 + 이전 누적합 - 온도값[(현재 인덱스 - 구해야하는 날짜)] 으로 구하도록 하였다.
이렇게 하면 각 인덱스에는 구해야하는 날짜만큼의 누적합이 담기게 된다.
그 후, 반복문을 돌면서 Max값을 구하면 그 값이 최종값이 되는 것이다.
또 하나 생각해야 할 부분이 있었는데, 값을 구할때 구해야 하는 날짜의 값보다 인덱스가 작은 경우 해당 온도 값을 그대로 저장하도록 해두었다.
이럴 경우, 구해야하는 날짜의 누적합보다 큰 값이 있을 경우 틀린 답이 나오게 된다.
예를 들어, [15, -3, 6, 1]이라는 값이 있고 2일간의 최대값을 구한다고 할 경우 누적합 배열은 다음과 같이 될 것이다.
| 15 | -3 | 6 | 1 |
| 15 | 12 | 3 | 7 |
이 경우, 제일 첫번째 값이 15이므로 최대값이 12가 아닌 15가 나오는 현상이 발생하게 된다.
따라서 나는 최종적으로 Max값을 계산할 때, 구해야하는 날짜 이후부터 계산을 하도록 하였다.
그럼 진짜 작성한 코드를 한번 살펴보자.
import java.io.*;
import java.util.*;
class Main {
public static int n, m;
public static long result;
public static String[] str;
public static int[] arr;
public static long[] temp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
str = br.readLine().split(" ");
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
str = br.readLine().split(" ");
arr = new int[n];
temp = new long[n+1];
result = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(str[i]);
}
temp[0] = arr[0];
for (int i = 1; i < n; i++) {
if (i < m) {
temp[i] = arr[i] + temp[i - 1];
} else {
temp[i] = arr[i] + temp[i - 1] - arr[i - m];
}
}
for (int i = m - 1; i < n; i++) {
result = Math.max(result, temp[i]);
}
System.out.println(result);
}
}우선 온도를 저장할 배열 arr와 누적합을 저장할 배열 temp를 선언하였다.
그리고 최종 값을 저장할 result 변수를 선언한다.
온도 배열을 입력 받은 후, 반복문을 순회하는데 해당 index 값이 계산일 m보다 작을 경우는 인덱스에 이전 날짜 값을 더했다.
(예를 들어 계산일이 5일인 경우, 1~4까지는 그냥 더해지기만 해야하기 때문이다)
반대로 index가 계산일 m보다 같거나 큰 경우, 앞서 설명한 대로 현재 index의 온도값 + 이전 index의 누적값 - (온도값[index - 계산일])을 통하여 계산일 m만큼의 누적합만을 계산해 내었다.
마지막으로 최종 계산된 누적합 배열을 순회하며 max값을 가져오는 로직이다.
이렇게 하면 한번만 반복하면 모든 최종 누적합을 구할 수 있으므로 시간 복잡도 면에서 상당한 효율을 가져 갈것이다.
