HackerRank 문제풀이 - 8 (Array Manipulation)

1. 문제

• 1부터 시작하는 인덱스가 지정된 배열과 연산 목록이 주어진다.
  • 각 연산은 시작 인덱스와 끝 인덱스 사이에 속한 배열 요소에 일정한 값을 더하는 작업이다.
  • 연산을 모두 수행한 후, 배열에서 가장 큰 값을 찾아 반환해야 한다.

 

 

2. 1차 문제풀이

2.1 풀이 과정

function arrayManipulation(n, queries) {
    // Write your code here

    const listLength = queries.length;
    console.log("n:", n);
    console.log("queries:", queries);
    console.log("listLength:", listLength);
    
    let resultList = [];
    
    for(let i = 0; i < n; i ++){
        resultList.push(0);
    }
    
    let maxVal = -1;
    for(let i = 0; i < listLength; i ++){
        const startIdx = queries[i][0];
        const endIdx = queries[i][1];
        const addVal = queries[i][2];
        
        for(let j = startIdx-1; j < endIdx; j++){
            resultList[j] += addVal;
            
            const currVal = resultList[j];
             if(currVal > maxVal) maxVal = currVal;
        }
        
        console.log("resultList:", resultList);
    }
    
    return maxVal;
}

풀이 과정은 다음과 같다.

• 주어진 연산 목록 ‘queries’의 각 연산에 대해 반복문을 실행한다.
  • 연산의 시작 인덱스부터 끝 인덱스까지 반복하여 배열 ‘resultList’의 해당 요소에 ‘addVal’을 더한다. 동시에 현재 요소의 값과 최대 값 ‘maxVal’을 비교하여 더 큰 값을 ‘maxVal’에 저장한다.
• 마지막으로 반복문이 완료된 후 ‘maxVal’을 반환한다.

 

2.2 풀이 결과

당연하게도 크기가 큰 데이터데 애해 Time Limit 실패가 되었다.

이 코드는 모든 연산을 처리하기 위해 두 개의 중첩된 반복문을 사용하므로 시간 복잡도가 O(n*m)이 될 수 있다. 개선된 알고리즘을 사용하여 선형 시간에 문제를 해결하는 것이 더 효율적일 수 있다.

 

 

 

3. 2차 문제풀이

3.1 풀이 과정

function arrayManipulation(n, queries) {
    const listLength = queries.length;
    console.log("n:", n);
    console.log("queries:", queries);
    console.log("listLength:", listLength);
    
    var arr = new Array(n).fill(0);
    
    for(let i = 0; i < listLength; i ++){
        const startIdx = queries[i][0];
        const endIdx = queries[i][1];
        const addVal = queries[i][2];
        
        arr = arr.map((val, index)=> {
            if(index >= startIdx && index <= endIdx){
                return val + addVal;
            } else {
                return val;
            }
        });
        
        console.log("arr:", arr);
    }
    
    return Math.max(...arr);
}

수정된 풀이 과정은 다음과 같다.

• 배열 ‘arr’을 ‘n’ 길이만큼 생성하고 0으로 초기화한다.
  • 연산 목록을 순회하며 각 연산에서 시작 인덱스’startIdx’, 끝 인덱스 ’endIdx’, 더할 값 ‘addVal’을 가져온다.
  • ‘arr’의 각 요소에 대해 ‘map‘ 함수를 사용하여 시작 인덱스와 끝 인덱스 사이인 경우에만 값을 ‘addVal’만큼 증가시킨다.
  • 최종적으로 ‘arr’에서 가장 큰 값을 찾아 반환한다.

 

위의 코드는 배열을 한번만 업데이트하고 최대 값을 찾기 위해 ‘map’함수를 사용하여 작업을 수행한다. 따라서 중첩된 반복문을 사용하지 않아 시간 복잡도가 O(n)으로 개선되었다.

 

 

3.2 풀이 결과

풀이 결과는 1차 풀이 결과와 동일하게 실패하였다.

그래서 3차 풀이에서는 비동기 방식으로 풀어가게 수정하였다.

 

 

 

 

4. 3차 문제풀이

4.1 풀이 과정

async function arrayManipulation(n, queries) {
    const listLength = queries.length;
    console.log("n:", n);
    console.log("queries:", queries);
    console.log("listLength:", listLength);
    
    var arr = new Array(n).fill(0);
    var maxVal = -1;
    
    const chunkSize = 10000;
    
    for(let chunkStart = 0; chunkStart < listLength; chunkStart += chunkSize){
        const chunkEnd = Math.min(chunkStart + chunkSize, listLength);
        const chunkQueries = queries.slice(chunkStart, chunkEnd);
        
        await Promise.all(chunkQueries.map(async (query)=> {
            const startIdx = query[0];
            const endIdx = query[1];
            const addVal = query[2];
            
            for(let i = startIdx; i <= endIdx; i++){
                arr[i] += addVal;
                if(arr[i] > maxVal){
                    maxVal = arr[i];
                }
            }
        }));
    }
    
    return maxVal;
}

풀이 과정은 다음과 같다.

• ‘chunkSize’변수는 연산 목록을 처리할때 한 번에 처리할 청크의 크기를 설정한다.
  • ‘listLength’를 기준으로 ‘chunckSize’만큼씩 청크를 나누어 연산을 수행한다. 각 청크에서는 ‘chunkQueries’에 현재 청크에 해당하는 연산 목록을 저장한다.
  • ‘Promise.all’과 ‘map’함수를 사용하여 비동기적으로 연산을 수행한다. 각 연산에서 시작 인덱스 ‘startIdx’, 끝 인덱스 ‘endIdx’, 더할 값 ‘addVal’을 가져온 후, 시작 인덱스부터 끝 인덱스까지 반복하며 배열 ‘arr’을 업데이트하고 최대 값을 갱신한다.
• 마지막으로, 구한 최대 값을 반환한다.

 

이 코드는 연산 목록을 청크 단위로 나누어 비동기적으로 처리하는 방식으로 동작한다. 이를 통해 대용량의 연산 목록을 효율적으로 처리할 수 있다.

 

4.2 풀이 결과

하지만, 1~2차때와 동일하게 Time limit이 발생하였다.

10만개가 넘는 데이터의 양도 비동기 방식으로는 30초 가량의 시간도 부족하였다.

그래서, 적절한 풀이 알고리즘을 찾게 되었다.

 

 

 

5. Prefix Sum(누적 합) 알고리즘 적용, 문제풀이

5.1 Prefix Sum(누적 합) 알고리즘이란?

Prefix Sum은 배열에서 각 인덱스까지의 값들을 누적하여 저장하는 방식을 말한다. 이를 통해 배열의 특정 범위에 대한 합을 빠르게 구할 수 있다.

 

예를 들어, ‘[1, 2, 3, 4, 5]’ 라는 배열이 있다고 가정하면, 이 배열의 Prefix Sum을 구하면 ‘[1, 3, 6, 10 15]’가 된다. 각 인덱스에는 해당 인덱스까지의 값들이 합이 저장되어 있다.

 

간단히 설명하면 위와 같다. 이를 적용하여 문제를 풀어보고자 한다.

 

 

5.2 풀이 과정

function arrayManipulation(n, queries) {
    const diff = new Array(n + 1).fill(0);
    let maxVal = 0;
    
    for(const [s, e, v] of queries){
        diff[s] += v;
        if(e + 1 <= n){
            diff[e + 1] -= v;
        }
    }
    
    let val = diff[0];
    for(let i = 1; i <= n; i++){
        val += diff[i];
        if(maxVal < val){
            maxVal = val;
        }
    }
    
    return maxVal;
}

풀이 과정은 다음과 같다.

• ‘diff’라는 배열을 생성하여 길이가 ‘n+1’이고 모든 요소가 0으로 초기화되도록 한다. 이 배열은 인덱스에 해당하는 값들의 변화량을 저장하기 위해 사용된다.
• ‘maxVal’ 변수는 최대 값을 추적하기 위해 0으로 초기화한다.
• ‘queries’ 의 각 연산 ‘[s, e, v]’ 에 대해 반복문을 실행한다. 시작 인덱스 ‘s’에 값을 더하고, 끝 인덱스’e’가 배열 범위를 초과하지 않는 경우에는 ‘e+1’위치의 값을 뺴서 배열 ‘diff’에 변화량을 저장한다.
• 다음으로, ‘diff’배열을 순회하며 각 위치에서 누적 값을 계산하고, 최대 값을 갱신한다. 이를 위해 ‘val’ 변수를 사용하여 누적 값을 추적한다.

마지막으로, 최대 값을 반환한다.

 

이 코드는 배열의 변화량을 효율적으로 계산하여 연산을 수행하고, 누적 값을 이용하여 최대 값을 찾는 방식으로 동작한다. 이를 통해 중첩된 반복문을 사용하지 않고도 좋은 성능으로 문제를 해결할 수 있다.

 

 

5.3 풀이 결과

적절한 알고리즘을 적용하니 빠른 시간내에 문제가 해결되었다.

역시 동기보다도 비동기, 비동기보다도 적절한 알고리즘 선택이

계산의 성능을 훨씬 향상시킬 수 있는듯 하다.