[Javascript] Codility Lesson9 - MaxDoubleSliceSum

 

https://namu.wiki/w/JavaScript

 

문제: https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

 

문제 요약

• 길이가 N인 배열 A가 주어지며 N의 범위는 3 ~ 100,000이다.
• 트리플렛 (X, Y, Z)가 주어지며 (0 ≤ X < Y < Z < N) 이는 A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1]를 의미한다.
• 모든 경우에서 최대합을 구하여라

 

풀이

function solution(A) {
    let forward = new Array(A.length).fill(0);
    let backward = new Array(A.length).fill(0);
    let result = 0;

    // 1) 
    for (let i = 1; i< A.length; i++) {
        forward[i] = Math.max(forward[i - 1] + A[i], 0);
    };

    // 2) 
    for (let i = A.length - 2; i > 0; i--) {
        backward[i] = Math.max(backward[i + 1] + A[i], 0);
    };
    
    // 3) 
    for (let i = 1; i< A.length - 1; i++) {
        result = Math.max(result, forward[i - 1] + backward[i + 1]);
    };

    return result;
}

하루정도 고민하다가 도저히 방법이 머릿속에 안 떠올라 다른 분이 푼 것을 보고 해결했다. 이마저도 한 번에 이해되지 않아 그림 그리면서 이해함ㅠㅠ 문제 해결 컨셉은 (X, Y, Z) 중 Y를 기준으로 왼쪽과 오른쪽을 나누고, 왼쪽의 최대합과 오른쪽의 최대합을 구하는 것이다.

일단 위 컨셉을 기억해 놓고 하나하나 설명해보겠다.

 

1) 0번째 인덱스부터 순서대로 배열 A를 순회하며 누적 값을 forward 배열에 저장한다. 
(forward[1] = forward[0] + A[1], forward[2] = forward[1] + A[2], forward[3] = forward[2] + A[3] ...)

 누적 값을 저장할 때 Math.max를 이용해 0과 저장할 값을 비교해 큰 값을 저장한다. 0과 비교하는 이유는 문제상에 X,Y,Z가 인접한 경우(ex: (1,2,3))의 최대합은 0이라고 나와있으며 즉 이 문제에서 나올 수 있는 최솟값은 0이라는 이야기이다. 

 

2) N-1번째 인덱스부터 역순으로 배열 A를 순회하며 누적값을 backward 배열에 저장하며, 이 역시도 1)번과 동일하게 0과 크기 비교를 하여 큰 값을 저장한다.

(backward[6] = backward[7] + A[6], backward[5] = backward[6] + A[5], backward[4] = backward[5] + A[4], ...)

 

3) 최종 결과값을 구하는 부분으로, 앞서 만든 배열 forward와 배열 backward을 이용하여 최대합을 구한다.

forward[0] + backward[2] = 0 + (A[2] ~ A[N-1] 누적값 중 최대 값)

forward[1] + backward[3] = A[1] + (A[3] ~ A[N-1] 누적값 중 최대 값)

forward[2] + backward[4] = (A[1] ~ A[2] 누적값 중 최대값) + (A[4] ~ A[N-1] 누적값 중 최대값)

forward와 backward 사이에 1을 떨어뜨리는 이유는 이 부분이 Y가 있어야하는 위치이기 때문이다.
(Y는 합산한 값에 속하지 않는다.)

 

 

알고리즘 문제 열심히 풀자...🥲

 

---

• https://sustainable-dev.tistory.com/25