PrefixSum

[dlehdanakf]

개요

• 부분합 관련하여 미리 합을 구하고 조건에 따라 값을 더하거나 빼며 정답을 찾는 알고리즘
• 조건에 따라 그때 그때 부분합을 계속 구한다면 시간복잡도가 대폭 증가하여 시간초과가 날 것이다.
• 부분합을 미리 구하고, 또 조건에 따라 추가하거나 빼기 위해서는 일정한 규칙에 따라 증감 연산을 수행해야한다.
• 보통은 0번 부터 끝번 까지 순서대로 부분합을 구하는 규칙으로 부분합 알고리즘을 활용한다.

예시

TapeEquilibrium

• 문제 바로가기
• 배열 A가 주어지고 P를 기준으로 이분할 때 나뉘어진 배열 A1 과 A2 의 부분합 차이가 가장 작아지는 P에서 부분합 차이를 구하는 문제.
• 이 문제에서 1, 2, ..., A-1 P에 대해 모든 경우에서 부분합을 구할 경우 아마 시간초과가 날 것이다. 부분합을 구하기 위해 계속 O(n)의 시간을 쓰기 때문

해결과정

• A 배열에 대해 P를 기준으로 A1, A2로 나뉘므로 A1의 부분합을 left 변수에, A2의 부분합을 right 변수에 미리 저장한다.
• 여기서 미리 저장한다는 뜻은 P가 0일 때 즉, 1부터 시작하는 P에 대해 시작하기 전의 값으로 미리 구해둔다는 뜻으로 당연 left는 0으로, right 는 A 원소들의 합으로 초기화된다.
• P가 1일 때는 left에 A[1] 값을 더해주고, right에는 빼준 뒤 두 부분합의 차이를 기록한다.
• 모든 P에 대해 가장 작은 값을 구한뒤 반환한다.

function solution(A) {
    let left = 0, right = A.reduce((acc, cur) => acc + cur, 0);
    let answer = Infinity;
    for(let i = 1; i < A.length; i++) {
        left += A[i - 1];
        right -= A[i - 1];

        const diff = Math.abs(left - right);
        answer = Math.min(answer, diff);
    }

    return answer;
}

[dlehdanakf]

쿠키 구입

• [문제 바로가기]()
• Prefix Sum 문제라기 보다는 Two Pointer 알고리즘 문제 같지만 일단 부분합을 사용하긴 하니까...뭐
• 쿠키를 구입할건데 배열 속에 쿠키 갯수가 담겨있다. 두 구간을 만들 때 구간합이 동일한 구간에 대해 최대 구간의 구간합은 몇인가?
• 범위를 나누는 기준점 세 개가 있다. l, m, r
• l ~ m, m + 1 ~ r 까지일 때 최대합이 되는 구간을 구하고 그 값을 반환하면 된다.

해결과정

• 부분합 배열을 먼저 만들어주어야한다. 부분합을 먼저 구해주지 않고 그때 그때 구간을 나눌 때마다 부분합을 구하려할 경우 시간초과는 당연하다.
• 배열 N이 있고 부분합 배열 PS가 있을 때, N 배열 l 부터 m 까지 구간의 합은 PS[m] - PS[l] 이다.
• 근데 고민거리는 위 문제에서 ㅣ ~ m 이라고 했는데 이는 l 번째 값을 포함하는 범위란거다. 즉, 엄밀히 말하면 PS[n] - PS[m - 1]을 해줘야 m 을 포함한 구간합을 구할 수 있다.
• 근데 m - 1을 할 때 만약 m 이 0이면 어떡하지? 그래서 첫 번째 원소를 0으로 두는 N 보다 원소의 개수가 한 개 많은 PS 배열을 만든다.
• 이렇게 해두면 m 을 포함한 구간합을 따로 예외처리 없이 편리하게 만들 수 있다. 스프레드 연산자를 이용하면 만들기도 쉽다.

function solution(cookie) {
    // 부분합 배열 만들기
    const PS = [0, ...cookie];
    for(let i = 1; i < PS.length; i++) {
        PS[i] += PS[i - 1];
    }

    let answer = 0;
    for(let m = 0; m < PS.length; m++) {
        const t = PS[m]; // 0 부터 m 까지 합
        for(let r = m + 1; r < PS.length; r++) {
            const right = PS[r] - t; // m + 1 부터 r 까지 합
            if(t < right || right <= answer) {
                // right 값이 answer 보다 작다면 계산해볼 필요가 없다.
                // right 값이 t 보다 크다면 t에서 더 줄여봤자 항상 right 값이 더 크므로 더 계산할 필요가 없다.
                continue;
            }

            for(let l = 0; l < m; l++) {
                const left = t - PS[l]; // l ~ m 까지 합
                if(left === right) {
                    // left 값과 right 값이 같다면 정답일 수 있다.
                    answer = Math.max(answer, left);
                } else if(left < right) {
                    // left 값이 right 보다 작다면 더 이상 부분합 구간을 줄여봤자 항상 작으므로 l 탐색을 멈춘다.
                    break;
                }
            }
        }
    }

    return answer;
}

• 이 문제를 푸는데 어려웠던 점은 먼저 어느 구간을 정해놓고 시작할 것인지 였다.
• l, m, r 세 점이 있을 때, l 부터 정하기 보다는 m을 먼저 정하는게 유리하다. l 부터 정할 경우 중간중간 더 이상 볼 필요가 없는 조건에 대해 조건문을 만들기가 애매하지만, 어쨌든 구간은 m 을 기준으로 나뉘는 만큼 l 가 정해지지 않은 상태에서도 조건문을 삽입하여 시간을 단축시킬 수 있다.
• 문제를 풀다보면 문제에서 주어지는, 해결방법처럼 제시되는 지문에 현혹되지 말고 최적의 방법이 무엇일지 생각해보자...(생각한다고 바로바로 떠올라야말이지)
• 삼중 반복문을 사용하는 코드지만 중간중간 조건문을 활용하여 더 이상 탐색할 필요가 없는 구간을 패스하게 만들어 시간을 단축시킬 수 있다. 애시당초 변수가 세 개인데 반복문 개수를 더 줄일 수 있는 방법이 있긴 할까...

[dlehdanakf]

보석쇼핑

• 문제 바로가기
• 매대 속 모든 종류의 보석을 구매할 수 있는 최소한의 구간을 구하시오

해결방법

• 처음 접근할 때는 Prefix Sum 알고리즘을 그대로 충실히 구현한 코드를 작성했다.
• 그리고 시간초과가 났다... 정확성 점수는 모두 맞았지만 효율성 점수는 0점이다 ㅋ
• 먼저 부분합을 구하기 위해 PS 배열을 선언하고 0 부터 i 까지 보석의 종류와 개수를 i번째 원소 Map 객체에 저장한다.
• 시작과 끝점 i 와 j 를 지정하고 PS[j] - PS[i] 연산을 한다. 하지만 이게 말이 연산이지 실제로는 모든 보석의 목록을 한바퀴 도는 O(n)의 시간이 필요한 작업이다. 아마 여기서 시간초과가 날 것이다.
• 0 <= j <= i <= N 인데 i 를 움직여서 먼저 모든 보석이 있는 구간부터 1 씩 증가한다.
• j 를 움직여 모든 보석이 있는 구간을 좁혀나간다.
• 그리고 시간초과가 나는 결과를 만나면 된다.

function solution(gems) {
    const PS = new Array(gems.length + 1).fill(undefined);
    PS[0] = new Map;
    for(let i = 1; i < PS.length; i++) {
        PS[i] = new Map(PS[i - 1]);

        const gem = gems[i - 1];
        PS[i].set(gem, (PS[i].get(gem) || 0) + 1);
    }

    const gem_categories = [...PS[PS.length - 1].keys()];
    const gem_diff = (a, b) => {
        for(const gem of gem_categories) {
            if((b.get(gem) || 0) - (a.get(gem) || 0) < 1) {
                return false;
            }
        }

        return true;
    };

    let _i = PS.length, _j = 1, gap = _i - _j;
    for(let i = gem_categories.length; i < PS.length; i++) {
        if(PS[i].size !== gem_categories.length) {
            continue;
        }

        for(let j = Math.max(i - gap, 1); j <= i; j++) {
            const c = gem_diff(PS[j - 1], PS[i]);
            if(c === true && i - j < gap) {
                gap = i - j; _i = i; _j = j;
            } else if(c === false) {
                break;
            }
        }
    }

    return [_j, _i];
}

• 혹시나 싶어 단순 투 포인터 알고리즘과 Array.prototype.slice 메소드를 활용해 코드를 작성해봤다.
• 당연하게도 slice 과정에 비용이 있어 정확성 점수를 체크할 때도 시간초과가 났다. 틀린 답은 없지만 시간이 꽤 많이 필요한 모양이다.
• slice 뿐만 아니라 Set 객체를 초기화하는 과정에서도 아마 비용이 발생하리라...

function solution(gems) {
    const gem_set = new Set(gems);
    const gem_size = (s, e) => (new Set(gems.slice(s, e))).size;

    let is_verified = false, gap = gems.length, _i, _j;
    for(let i = gem_set.size - 1; i < gems.length; i++) {
        if(gem_size(0, i + 1) !== gem_set.size) {
            continue;
        }

        for(let j = 0; j <= i; j++) {
            const c = gem_size(j, i + 1) === gem_set.size;
            if(c === true && i - j < gap) {
                gap = i - j, _i = i, _j = j;
            } else if(c === false) {
                break;
            }
        }
    }

    return [_j + 1, _i + 1];
}

• 결국 포기하고 다른 사람의 풀이를 보았다.
• 세상에 이렇게 푸는 사람도 있나... 애초에 배열의 길이가 너무나도 길게 주어지기 때문에 i 와 j 를 별개로 구하는, 즉 반복문이 두 개 이상 사용하면 무조건 시간초과가 발생하는 문제였다.
• O(n) 시간으로 문제를 풀어야만 한다. 방법은 Map 객체를 사용한다.
• 해설을 본 뒤 소스코드를 작성해보았다. 해설 바로가기

function solution(gems) {
    const { size } = new Set(gems);
    const obj = new Map;

    let _i, _j;
    gems.forEach((gem, i) => {
        obj.delete(gem);
        obj.set(gem, i);

        if(obj.size === size) {
            // const [ j ] = [...obj.values()];
            const { value: j } = obj.values().next();
            if(_j === undefined || _i - _j > i - j) {
                _i = i;
                _j = j;
            }
        }
    });

    return [_j + 1, _i + 1];
}

• 위에서 Map.prototype.delete 메소드를 굳이 호출하는 이유는 단순 set 작업만 반복할 경우 Map.prototype.values 메소드를 호출했을 때 값들의 순서가 바뀌지 않기 때문이다.
• 가장 처음에 Map 객체에 삽입(?)되었던 값의 인덱스를 가져와야하는데 set 작업만 반복된다면 영원히 gems[0] 만 찾을 수 있을 것이다. delete 메소드를 통해 "수정"이 아닌 "삭제 후 삽입"이 이루어져야한다.
• 심지어 const [ j ] = [...obj.values()] 코드로 j 값을 가져오면 시간초과가 발생한다. 아무래도 MapIterator 객체에서 배열로 초기화하는 비용 때문인 것 같다. 보석의 종류가 정말 다양하다면 아무래도 이 작업 또한 시간이 제법 소요될 것이다.
• values 메소드를 호출했으면 불편하더라도 그냥 MapIterator 객체를 그대로 사용하자. 해당 객체를 스프레드 연산자로 배열화 하는 것도 시간효율성 측면에서 안좋다.
• 세상에 세상에... 상상도 못했던 방법이다.