[programmers/py] 연속 펄스 부분 수열의 합

연속 펄스 부분 수열의 합

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

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.

정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

풀이

sequence를 (-1,1), (1,-1) 두 개의 펄스 수열로 곱해진 누적합 dp1, dp2을 구합니다.
각 누적 합에서 최댓값 - 최솟값을 구해 더 큰 값을 반환합니다.

이때, 누적합의 길이를 N으로 설정하면 전체가 음수 또는 양수로 이루어진 경우 0+-N, 0+N이 우리가 구해야하는 x,y 값인데 -N+-M, N+M처럼 다른 값이 나오게 됩니다. N+1을 통해 0을 처음에 넣어야 함

def solution(sequence):
    N = len(sequence)
    pulse1 = [1, -1]
    pulse2 = [-1, 1]
    dp1 = [0] * (N+1)
    dp2 = [0] * (N+1)

    for i, s in enumerate(sequence):
        dp1[i+1] = dp1[i] + s*pulse1[i%2]
        dp2[i+1] = dp2[i] + s*pulse2[i%2]
    
    x = max(dp1) - min(dp1)
    y = max(dp2) - min(dp2)
    return max(x, y)

다른 사람 풀이

두 개의 수열을 만들 필요 없이 하나의 수열만 구해도 답을 구할 수 잇다.

def solution(sequence):
   n = len(sequence)
   psum = [0] * (n+1)

   for i in range(n):
       psum[i+1] = psum[i] + sequence[i]*(-1)**i;

   return max(psum) - min(psum)