프로그래머스 코딩테스트 - 연속 펄스 부분 수열의 합

문제

https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

해결 방법

방법1: Dynamic Programming

지난 포스팅에서 사용했던 dp를 재적용해봤다.

펄스 수열이 [1, -1, 1, ...] 처럼 1부터 시작하는 것과 [-1, 1, -1, ...] 처럼 -1부터 시작하는 수열이 있기 때문에 양수 펄스 수열을 적용한 전체 수열과 음수 펄스를 적용한 수열을 저장할 plus 배열을 생성했다.

plus	2	-3	-6	-1	3	1	2	-4
	-2	3	6	1	-3	-1	-2	4

순서대로 위에는 1로 시작하는 펄스 수열을 적용한 결과이고 아래는 -1부터 시작하는 펄스 수열을 적용했다.

 

이제 수열의 부분 합을 구할 것인데 시작부터 수열의 합을 구하다가 수열의 합이 현재 수열의 수보다 작을 때는 현재의 수부터 다시 수열의 합을 구하도록 한다. 그러면 부분 수열의 합이 아래와 같아진다.

즉, plus[i] + acc[i-1]과 plus[i]를 비교해서 더 큰 값을 acc 배열에 추가하는 방식으로 진행한다.

acc	2	-1	-6	-1	3	4	6	2
	-2	3	9	10	7	6	4	8

 

acc 배열 전체 중 가장 큰 값이 부분 수열의 최대 합이 된다.

코드

function solution(sequence) {
    var answer = 0;
    const len = sequence.length
    const basic = Array.from({ length: len }, () => 0)
    
    const plus = Array.from({ length: 2 }, () => [...basic]);
    const acc = Array.from({ length: 2 }, () => [...basic]);
    
    for (let i = 0; i < len; i++) {
        if (i < 1) {
            plus[0][i] = sequence[0];
            plus[1][i] = -sequence[0];
            
            acc[0][i] = plus[0][i];
            acc[1][i] = plus[1][i];
            
            answer = Math.max(answer, acc[0][i], acc[1][0])
            continue;
        }
        
        const sign = i % 2 === 0 ? 1 : -1
        plus[0][i] = sign * sequence[i];
        plus[1][i] = -1 * sign * sequence[i];
        
        acc[0][i] = Math.max(plus[0][i] + acc[0][i-1], plus[0][i]);
        acc[1][i] = Math.max(plus[1][i] + acc[1][i-1], plus[1][i]);
        
        answer = Math.max(answer, acc[0][i], acc[1][i])
    }
    return answer;
}

 

방법 2: 누적합

이건 풀이를 끝낸 후 다른 사람들의 코드를 보면서 알게된 풀이방법이다.

중요한 아이디어는 펄스함수를 하나만 고려하며, 누적 합의 최댓값과 최소값의 차를 통해 부분 수열의 최대 합을 구한다는 것이다.

 

어떻게 가능할까?

일단 위에서 구한 plus 배열의 누적 합을 구해보겠다.

sum	2	-1	-7	-8	-5	-4	-2	-6
	-2	1	7	8	5	4	2	6

그럼 위와 같이 펄스 수열을 적용한 후 구한 합은 정확이 부호만 반전된 결과를 낸다.

따라서 우리는 두 경우를 모두 고려할 필요없이 하나의 경우만 활용해도 누적합을 구할 수 있게 되는 것이다.

function solution(sequence) {
    let max = 0, min = 0;
    let sum = min
    sequence.forEach((s, idx) => {
        sum += s * (-1)**idx
        max = Math.max(sum, max)
        min = Math.min(sum, min)
    })
    
    return max === min ? max : max - min
}

결과