[해커랭크] 알고리즘을 최적화 해보자 Array Manipulation

Hacker Rank - Interview Preparation Kit

category - [Array]

language - [javascript]

 

3. Array Manipultation

www.hackerrank.com/challenges/crush/problem

Array Manipulation | HackerRank

 

---

 

[문제 선정의 이유]

하드를 얕보면 안된다

무려 Hard 난이도의 문제이다.

쉬워 보인다고 후루룩 풀고 넘어가려다가는 서브미션에서 절반이 넘는 테스트 케이스가 타임오버 나가리를 맞게 된다는 뜻이다.

이 문제의 핵심은 푸는데 있는 것이 아니라 최적화를 통해 BigO를 때려 잡는 데에 있다. 

 

---

 

[문제 내용]

1. 초기 값이 모두 0으로 채워진 길이가 n인 배열에 값을 더하는 m번의 쿼리가 들어온다.
2. 쿼리는 시작 인덱스a와 끝 인덱스b로 범위를 표기하고 거기에 해당하는 값 k를 마지막으로 표기한다.
3. n, m, a, b, k의 범위는 다음과 같다.

 

인덱스 a,b가 1부터 시작함을 주의

인풋은 n, m이 먼저 차례로 들어오고 쿼리 [a,b,k]가 들어있는 길이가 m인 2차원 배열 queries가 들어온다.

아웃풋은 모든 쿼리의 수행이 끝난 후 최종 배열에서 최댓값을 리턴하면 된다.

 

---

 

[잘못된 풀이]

js 기준으로는 첫번째 파라미터로 배열의 길이가, 두번째 파라미터로 쿼리 배열이 들어온다.

단순히 모든 쿼리를 돌면서 시작 인덱스 a부터 b까지 배열을 순회화며 값에 k를 더해주는 업데이트 작업을 반복하고 업데이트가 될 때 마다 최댓값을 확인하는 식으로 생각을 한다면 코드는 다음과 같을 것이고 답도 나오긴 나온다.

function arrayManipulation(n, queries) {
    let max=0;
    queries.reduce((acc,cur)=>{
        let start = cur[0]-1;
        let end   = cur[1]; 
        let val   = cur[2];
        for(let i=start; i<end; i++){
            acc[i]+=val;
            if(acc[i]>max) max = acc[i];
        }
        return acc;
    },(new Array(n).fill(0)));
    return max;
}

하지만 이전 문제에서도 지적했듯이 시간복잡도가 곱연산이 되는 상황은 결코 바람직하지 않다. 

 

위에서 주어진 범위표대로 n이 10⁷ 인 배열에 m이 2*10⁵ 인 쿼리가 꽉꽉 채워 들어오는데 모든 쿼리의 시작 인덱스 a가 1, 끝 인덱스 b가 n과 동일한 최악의 경우를 가정해 보자. 각 쿼리에서 시작 인덱스과 끝 인덱스까지 배열을 순회하며 k를 더해주는 작업을 반복하다가는 10⁷의 수행을 2*10⁵번 반복하는 어마무시한 짓을 하게 된다. 

 

이런 비현실적인 알고리즘을 최적화하기 위해서 시간복잡도를 어떻게 줄일 수 있을까?

 

차근차근 생각해 본다면 일단 쿼리 배열을 돌면서 모든 쿼리를 수행해야 하는 것 만큼은 어쩔 수 없기 떄문에 쿼리 배열의 길이인m은 더이상 줄일 수 없다는 것을 알 수 있다. 바꿔 말하면 매 쿼리 수행에 걸리는 (b-a+1)의 크기는 어떻게든 줄여봐야 한다는 결론이 나온다.

 

배열을 무식하게 돌면서 값을 일일히 더해주는 방법이 아닌 어떤 획기적인 방법으로 탈바꿈 할 수 있는지만 고민해보자.

 

---

 

[최적화]

사실 답은 문제 안에 있다. 정확히 말하자면 주어진 인풋의 형태가 힌트가 된다.

배열 arr에 대해 인덱스 a부터 b까지 값 k가 더해진 다는 것은 곧 a에서 k값이 추가되고 b이후부터는 k 값이 소멸한다고도 할 수 있다. a와 b는 1부터 시작하는 것을 주의해 값이 추가되는 지점과 소멸하는 지점만 표기하면 다음과 같다.

 

arr[a-1] += k;

arr[b] -= k;

(왜 a는 -1을 해주고 b는 하지 않았는지 생각해보자)

 

이걸 모든 쿼리를 돌면서 수행하게 하는 식은 다음과 같이 세울 수 있다.

const arr = queries.reduce((acc,cur)=>{
    let start = cur[0]-1;
    let end   = cur[1]; 
    let val   = cur[2];
    acc[start] += val;
    acc[end]   -= val;
    return acc;
},(new Array(n+1).fill(0)));

(초기 배열을 생성 할 때 위와 다르게 n+1의 크기로 초기화 한 이유는 무엇일까? arr[b] -= k와 연관지어 생각해보자) 

 

기존에는 m번동안 (b-a+1)번의 연산을 반복한 것과 다르게 단 두번씩만 배열에 접근한다. 무려 Big O에서 생략까지 가능한 상수값이다. 즉 시간복잡도는 쿼리배열의 길이인 m만 표기해도 무관할 정도로 연산이 줄었다.

 

이렇게 모든 쿼리의 표기가 완료된(엄밀히 말하면 쿼리가 수행된 상태의 배열은 아니다.) 배열 arr에서 최대 원소를 찾는 방법은 생각보다 간단하다. 배열 arr을 순회하며 원소를 더해 sum에 저장하고 최댓값을 저장하는 max와 비교해가며 max를 업데이트 해주면 된다.

let max=0, sum=0;

arr.forEach((v)=>{
    sum+=v;
    max = Math.max(sum,max);
});

 

arr의 각 원소를 0번 인덱스부터 더해가야 알 수 있는 이유는 우리가 쿼리의 생성과 소멸을 한번씩만 표기해 주었기 때문이다. 

arr의 N번째 값 arr[N]에 대해 인덱스 N이 포함되는 범위에서 k값이 더해지는 쿼리가 있었다면 시작 인덱스 a지점에서 k가 더해졌을 것이고 그 값이 N번째까지 유지된다. 만약 N이전에 해당 쿼리의 끝 인덱스 b가 있었다면 N에 도달하기 이전에 arr[b] -= k로 인해 arr[b]의 원소를 더하는 과정에서 소멸된다. a' b' k' 등으로 이루어진 다른 수많은 쿼리들이 중첩되어 있어도 원리는 같다. 따라서 arr[N]의 값은 arr[0] + arr[1] + ...  + arr[N]으로 알 수 있는 것이다.

 

이때의 연산은 arr의 크기인 n만큼, 엄밀히 따지자면 index out of range를 피하기 위해 arr의 크기를 n+1로 설정해주었으니 n+1만큼이 걸린다.

 

 

이제 두개의 큰 덩어리를 합쳐준 최종 함수는 다음과 같이 탈바꿈 하게된다.

function arrayManipulation(n, queries) {
    let max=0, sum=0;
    
    const arr = queries.reduce((acc,cur)=>{
        let start = cur[0]-1;
        let end   = cur[1]; 
        let val   = cur[2];
        acc[start] += val;
        acc[end]   -= val;
        return acc;
    },(new Array(n+1).fill(0)));

    arr.forEach(v=>{
        sum+=v;
        max = Math.max(sum,max);
    });

    return max;
}

최종적으로 도출되는 시간복잡도는 쿼리 수행에 걸린 m과 최댓값을 찾는 n이 합연산으로 이루어진 O(m+n)이 된다.

 

끔찍했던 Your code did not execute within the time limits 를 탈출해 모든 테스트 케이스가 무사히 통과하는 기쁨을 맛보면 마법같은 최적화의 힘을 느낄 수 있다.

 

---