배열 조작 JavaScript 솔루션

문제 설명

0의 1-인덱스 배열과 연산 목록으로 시작하여 각 연산에 ​​대해 주어진 두 인덱스(포함) 사이의 각 배열 요소에 값을 추가합니다. 모든 작업이 수행되면 배열의 최대값을 반환합니다.

설정

작성 중인 함수는 두 개의 인수를 사용합니다. 첫 번째 인수 n은 작업을 수행하는 배열의 요소 수를 나타냅니다. 두 번째 인수인 쿼리는 배열에서 수행할 작업의 배열입니다. 쿼리의 각 요소는 시작 인덱스, 끝 인덱스 및 시작 인덱스와 끝 인덱스 사이의 배열 요소에 추가할 값으로 구성된 배열입니다.

예시

n = 12;
queries = [
// Start, end, value to add
    [2,   7,   4],
    [5,   9,   2],
    [6,   12,  8]
]
/*
 1   2   3   4   5   6   7   8   9   10  11  12 // Indices
*/
[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0] // Starting array
[0,  4,  4,  4,  4,  4,  4,  0,  0,  0,  0,  0] // After queries[0]
[0,  4,  4,  4,  6,  6,  6,  2,  2,  0,  0,  0] // After queries[1]
[0,  4,  4,  4,  6,  14, 14, 10, 10, 8,  8,  8] // After queries[2]

largest = 10

순진한 접근 방식(무차별 대입)

길이가 n + 1인 배열을 만듭니다.

배열의 각 요소를 0으로 초기화합니다.

발생한 최대값을 저장할 변수를 생성하고 0으로 초기화합니다.

쿼리 배열을 반복하여 a, b, k를 분리합니다.

인덱스 a에서 b까지 배열을 순환하면서 해당 인덱스의 각 요소를 k만큼 증가시킵니다.

현재 인덱스에서 업데이트된 배열 값이 최대값보다 크면 최대값을 업데이트하십시오.

function arrayManipulation(n, queries) {
    let arr = new Array(n + 1).fill(0);
    let max = 0;
    queries.forEach(([a, b, k]) => {
        for (let i = a; i <= b; i++) {
            arr[i] += k;
            if (arr[i] > max) {
                max = arr[i];
            }
        }
    })
    return max
}

이제 이것은 일부 입력에 대해 작동합니다. 그러나 n이 큰 수일 때 어떤 일이 발생하는지 생각해 보십시오. 쿼리가 큰 배열인 경우 어떤 일이 발생하는지 생각해 보십시오. 쿼리의 각 작업에서 배열의 1-n 요소를 업데이트합니다. 수행할 작업이 많습니다. 따라서 솔루션으로 이와 같은 기능이 있는 경우 이 특정 문제에 대한 HackerRank의 일부 테스트가 시간 초과됩니다. 이 알고리즘을 사용하기에는 입력이 너무 큽니다. 웜프 웜프. 슬픈 트롬본.

하지만 뭔지 알아? 이 문제를 해결하는 방법을 모른다는 것은 부끄러운 일이 아닙니다. 어렵다고 표시되어 있습니다. 이 문제를 대규모로 해결하는 방법을 찾기 위해 토론 섹션에서 솔루션을 찾아야 했습니다. 그런 다음 제공된 솔루션이 어떻게 작동하는지 이해하기 위해 몇 가지 문제를 해결하기 위해 종이와 펜을 꺼내야 했습니다. 이것은 일단 이해하면 분명한 솔루션 중 하나입니다. 그리고 아름답습니다. 당연히 내가 찾은 솔루션은 모두 C++ 또는 Java로 되어 있었고 코드 문제에 대해 내가 선택한 언어가 아니므로 이를 JavaScript에 적용하여 이해했는지 확인하고 JavaScript로 해결하려는 사람이 더 쉽게 만들 수 있도록 했습니다. .

해결책

스포일러!

function arrayManipulation(n, queries) {
    let arr = new Array(n + 1).fill(0);
    queries.forEach(([a, b, k]) => {
        arr[a - 1] += k;
        arr[b] -= k;
    })
    let sum = 0;
    let max = 0;
    arr.forEach(val => {
        sum += val;
        max = Math.max(sum, max)
    })
    return max;
}

이전 예제를 사용하여 이것이 어떻게 작동하는지 살펴보겠습니다. arr[a - 1]에서 값을 변경하는 이유는 문제 문이 배열이 1-인덱싱됨을 나타내므로 JavaScript의 배열이 0-이기 때문에 주어진 배열 인덱스가 1만큼 꺼질 것이라고 표시했기 때문입니다. 인덱싱되었습니다. arr[b-1]이 아닌 arr[b]를 변경하는 이유는 작업이 에서 b까지 포함되어야 하기 때문입니다.

n = 12;
queries = [
// Start, end, value to add
    [2,   7,   4],
    [5,   9,   2],
    [6,   12,  8]
]
/*
 1   2   3   4   5   6   7   8  9  10 11  12  13 // Indices
*/
 [0, 0,  0,  0,  0,  0,  0,  0, 0,  0, 0,  0,  0] // Starting array
 [0, 4,  0,  0,  0,  0,  0, -4, 0,  0, 0,  0,  0] // After [2,7,4]
 [0, 4,  0,  0,  2,  0,  0, -4, 0, -2, 0,  0,  0] // After [5,9,2]
 [0, 4,  0,  0,  2,  8,  0, -4, 0, -2, 0,  0, -8] // After [6,12,8]

sum = 0, max = 0, arr = [0,4,0,0,2,8,0,-4,0,-2,0,0,-8]
sum += 0; // sum stays 0, max stays 0
sum += 4; // sum is now 4, sum > max, so max becomes 4
sum += 0; // sum stays same, max stays same
sum += 0; // sum stays same, max stays same
sum += 2; // sum is now 6; sum > max, so max becomes 6;
sum += 8; // sum is now 14; sum > max, so max becomes 14;
sum += 0; // sum stays same, max stays same
sum += -4; // sum is 10; max > sum, so max stays 14;
sum += 0; // sum stays same, max stays same
sum += -2; // sum is 8; max > sum, so max stays 14;
sum += 0; // sum stays same, max stays same
sum += 0; // sum stays same, max stays same
sum += -8; // sum is 0; max > sum, so stays 14;

max = 14;

어떻게 작동합니까? 글쎄, 우리는 끝 인덱스 다음의 인덱스에서 k의 값을 빼기 때문에, 우리는 그 k를 추가했어야 하는 인덱스에 대해 주어진 k의 값만 더하는 것입니다. 그리고 작업의 시작과 끝을 표시하기 위해 배열의 값만 변경하기 때문에 각 쿼리에 대해 2개의 업데이트만 수행합니다. 최악의 경우 복잡도가 n인 변수 연산을 상수로 변경했습니다! 너무 초라하지 않습니다.




HackerRank에서 가져온 문제