https://school.programmers.co.kr/learn/courses/30/lessons/181883
주말에 알고리즘 풀이를 하면서 좀 더 좋은 알고리즘은 없을까? 라는 의문에 작성하게 되었다.
위 문제에 풀이한 기존 코드는 다음과 같다.
class Solution {
public int[] solution(int[] arr, int[][] queries) {
for(int[] query : queries){
int s = query[0];
int e = query[1];
for(int i = s; i <= e; i++){
arr[i] += 1;
}
}
return arr;
}
}그러나 크기가 커지는 만큼 이 코드의 효율도 떨어진다. for문 안에 for문을 풀이하고 있으므로 시간 복잡도가 커진다.
queries가 N, arr.length가 M이라 하면, 시간 복잡도는 O(N * M)이 된다.
곱연산이므로 갈수록 계산 속도가 느려 품질 낮은 코드가 될 것이다.
좀 더 좋은 것은 없을까?
차분 배열(Difference Array)
이 알고리즘은 배열의 부분 구간에 변화만을 기록하고, 이를 바탕으로 계산한다.
프로세스
- 차분 배열을 선언하고 변화를 기록한다.
- 2개의 인덱스를 수정하여 반복한다.
- 모든 변화 기록이 끝났으면, 배열을 한 번만 순회하여 처리한다.
구간 업데이트 방법
- [s,e]가 주어졌을 경우, 시작 인덱스인 s에는 +1을 한다.
- 끝 인덱스 e+1 에는 -1를 한다. 이유는 끝 인덱스 이후의 값에 영향을 미치지 않기 위함이다.
예로 arr = [0, 1, 2, 3, 4]이고 queries = [[1, 3]]이라면, 차분 배열 diff는 다음과 같이 바뀐다.
diff[1] += 1; // s 인덱스에 +1
diff[4] -= 1; // e+1 인덱스에 -1최종 배열을 얻는 방법
- diff의 처리가 끝났으면 arr와 합산하여 최종 배열을 얻는다.
- arr[i]와 diff[i]를 더하면서, 이전 값들을 누적해나간다.
- 차분 배열 diff의 값이 변화하는 구간에만 영향을 주기 때문에, 그 범위 밖의 값들은 업데이트되지 않게 만든다.
arr = [0, 1, 2, 3, 4]
diff = [0, 1, 0, 0, -1]
1번째 배열은 그냥 더해줌.
arr[0] = arr[0] + diff[0] = 0 + 0 = 0
arr[1] = arr[1] + diff[1] = 1 + 1 = 2
arr[2] = arr[2] + diff[2] = 2 + 0 = 2
arr[3] = arr[3] + diff[3] = 3 + 0 = 3
arr[4] = arr[4] + diff[4] = 4 - 1 = 3
최종 결과: [0, 2, 2, 3, 3]
arr.length + 1 로 선언하는 이유
차열 배열은 e+1에 -1를 처리한다. 그렇다면 마지막 요소까지 범위라면?
e+1이 없으므로 에러가 난다.
e가 배열의 마지막 인덱스일 때는 e + 1이 배열의 크기와 동일하므로, 차분 배열의 크기가 arr.length + 1이어야 e + 1을 안전하게 다룰 수 있다.
그래서 arr.length + 1로 diff를 선언하는 것이다.
그래서 왜 쓰는건데?
시간 복잡도가 매우 효율적으로 바뀐다. 프로그래머스의 문제에 차분 배열을 적용한 코드를 보자
import java.util.*;
class Solution {
public int[] solution(int[] arr, int[][] queries) {
// 차분 배열 초기화
int[] diff = new int[arr.length + 1]; // 마지막 인덱스 처리하기 위해 +1
// 쿼리 처리: 구간 [s, e]에 대해 차분 배열 갱신
for (int[] query : queries) {
int s = query[0];
int e = query[1];
// s번째 인덱스에 1을 더하고, e+1번째 인덱스에 -1을 처리한다.
diff[s] += 1;
if (e + 1 < diff.length) {
diff[e + 1] -= 1;
}
// 중간 차분 배열 상태 출력
//System.out.println("After query " + Arrays.toString(query) + ": " + Arrays.toString(diff));
}
// 차분 배열 최종 상태 출력
//System.out.println();
//System.out.println("Final diff array: " + Arrays.toString(diff));
//System.out.println();
int[] result = new int[arr.length];
result[0] = arr[0] + diff[0]; // 첫 번째 원소는 diff[0]을 더해줌
// 차분 배열 누적합을 계산하여 최종 결과 배열 생성
for (int i = 1; i < result.length; i++) {
diff[i] += diff[i - 1]; // 차분 배열을 누적합으로 변환
result[i] = arr[i] + diff[i]; // 원래 값과 차분 배열 값을 더하여 최종값 계산
// 중간 결과 출력
//System.out.println("result[" + i + "] = " + result[i] + " (arr[" + i + "] = " + arr[i] + " + diff[" + i + "] = " + diff[i] + ")");
}
return result;
}
}
입력값 〉 [0, 1, 2, 3, 4], [[0, 1], [1, 2], [2, 3]]
결과값 〉 [1, 3, 4, 4, 4]
After query [0, 1]: [1, 0, -1, 0, 0, 0]
After query [1, 2]: [1, 1, -1, -1, 0, 0]
After query [2, 3]: [1, 1, 0, -1, -1, 0]
Final diff array: [1, 1, 0, -1, -1, 0]
result[1] = 3 (arr[1] = 1 + diff[1] = 2)
result[2] = 4 (arr[2] = 2 + diff[2] = 2)
result[3] = 4 (arr[3] = 3 + diff[3] = 1)
result[4] = 4 (arr[4] = 4 + diff[4] = 0)
기초 코드는 O(N * M)으로 갈수록 효율이 떨어졌다.
이 코드에서는
1. 쿼리 처리가 O(1) 방식으로 추가된다.
2. Query 마다 반복되므로 Query의 길이만큼 O(N) 시간이 걸린다.
3. 차분 배열 계산이 끝난 후 누적합을 계산할 경우 O(M) 시간이 걸린다.
즉 O(N + M)으로 곱연산에서 합연산으로 효율이 달라진 것을 알 수 있다.
즉 핵심은 구간 업데이트가 필요할 때 한 번에 변경 사항만 기록하고, 최종 배열을 계산할 때 누적합을 통해 실제 결과를 도출하기 위함이다.
이를 통해 성능이 개선되기 떄문이다.
