[ Algorithm ] 차분 배열 ( Difference Array ) 기법

프로그래머스

 

위 프로그래머스 "수열과 구간 쿼리" 문제를 풀다가 차분 배열이라는 것을 알게되었습니다.

기존에 제가 작성한 코드는 아래와 같습니다.

import Foundation

func solution(_ arr:[Int], _ queries:[[Int]]) -> [Int] {
    var result = arr
    
    for query in queries {
        let s = query[0]
        let e = query[1]
        
        for i in s...e {
            result[i] += 1
        }
    }
    return result
}

 

틀린 답은 아니지만 다른 사람들은 어떻게 풀었을까 찾아보던 과정 중 차분 배열로 푼 예시가 있어 차분 배열이란것이 무엇인지 알아보려 합니다.

차분 배열 ( Difference Array ) 기법이란?

 

• 특정 구간 [s, e]에 대해 한 번의 연산으로 전체 범위 값을 조작하는 방법
• arr[i]에 직접 값을 더하는 대신 **차분 배열(diff array)**을 사용해서 값의 변화만 기록
• 마지막에 **누적 합(Prefix Sum)**을 계산하면 arr이 완성

---

차분 배열을 적용하는 방식

diff[s] += 1   // 시작점 s에서 1 증가
diff[e + 1] -= 1  // 끝점 e의 다음 위치에서 -1 (변화를 중지)

 

---

차분 배열로 변경한 코드

 

func solution(_ arr: [Int], _ queries: [[Int]]) -> [Int] {
    var arr = arr
    var diff = Array(repeating: 0, count: arr.count + 1)  // 차분 배열

    // 차분 배열을 업데이트
    for query in queries {
        let s = query[0]
        let e = query[1]

        diff[s] += 1   // s부터 증가
        if e + 1 < diff.count {
            diff[e + 1] -= 1  // e+1부터 감소
        }
    }

    // 누적 합을 통해 원래 배열 값 업데이트
    var increment = 0
    for i in 0..<arr.count {
        increment += diff[i]
        arr[i] += increment
    }
    
    return arr
}

 

queries 적용 (차분 배열 만들기)

인덱스	diff 초기값	[1, 3]적용	[0, 2]적용	[0, 2]적용
0	0	0	+1	+1
1	0	+1	+1	+1
2	0	+1	+1	+1
3	0	+1	0	0
4	0	0	0	+1
5	0	-1	-1	-1

차분 배열 최종 상태

diff = [1, 1, 1, 1, 1, -3]

 

diff를 누적 합하여 arr 업데이트

1. increment = 0
2. arr[0] += (increment += diff[0]) → arr[0] = 1
3. arr[1] += (increment += diff[1]) → arr[1] = 2
4. arr[2] += (increment += diff[2]) → arr[2] = 3
5. arr[3] += (increment += diff[3]) → arr[3] = 2
6. arr[4] += (increment += diff[4]) → arr[4] = 1

최종 결과

[1, 2, 3, 2, 1]

---

차분 배열 기법의 핵심

1. diff[s] += 1 → s부터 증가를 시작
2. diff[e + 1] -= 1 → e 이후부터 증가 중지
3. 마지막에 누적 합(Prefix Sum) 계산으로 arr을 완성

---

차분 배열 기법을 써야 하는 이유

방법	시간 복잡도	설명
기본 for 문 (O(N*M))	O(N*M)	쿼리 수(M)가 많으면 느려짐
차분 배열 (O(N + M))	O(N + M)	대량의 쿼리를 빠르게 처리 가능