[프로그래머스] 연속 펄스 부분 수열의 합 Python 풀이

 

---

문제

---

구현

sequence에 [-1, 1, -1, 1......] 을 곱한 pulse배열과

sequence에 [1, -1, 1, -1......] 을 곱한 revpulse배열을 준비한다.

 

여기서 편의를 위해 accumulate 함수를 사용할 건데 배열을 돌며 이전 값에 따른 처리(기본 덧셈)를 해주는 함수이다.

코드 부분에서 추가로 설명하겠다.

 

그렇게 되면 각 배열 인덱스에 더해진 값이 있을건데 그중의 max값을 리턴하면 된다.

---

코드

from itertools import accumulate

def solution(sequence):
    pulse = [((-1)**(i%2))*sequence[i] for i in range(len(sequence))]
    revpulse = [i*-1 for i in pulse]

    arr=[]
    arr.append(list(accumulate(pulse, lambda x, y: max(y, x+y))))    
    arr.append(list(accumulate(revpulse, lambda x, y: max(y, x+y))))
    result = -float('inf')
    
    for ar in arr:
        result = max(result, max(ar))
    
    return result

accumulate에 관해 이어서 설명을 하기 위해 예제의 입력을 예로 들겠다.

[2, 3, -6, 1, 3, -1, 2, 4]에 [-1, 1, -1....]을 곱해주면

[-2, 3, 6, 1, -3, -1, -2, 4]가 나온다.

이를 더해줄건데 이전+현재의 값보다 현재의 값이 더 크면 더하지 않고 현재의 값을 리턴할 것이다.

accumulate의 결과는 [-2, 3, 9, 10, 7, 6, 4, 8] 이 된다.

 

이중에 가장 큰 10을 리턴하면 된다.

---

다른 풀이

def solution(sequence):
    table = [[0 for _ in range(len(sequence) + 1)] for _ in range(2)]
    weight = 1
    for i in range(len(sequence)):
        table[0][i + 1] = table[0][i] + sequence[i] * weight
        table[1][i + 1] = table[1][i] - sequence[i] * weight
        weight *= -1
    return max(max(table[0]) - min(table[0]), max(table[1]) - min(table[1]))

이거는 조금 더 생각해 보면 되는데 

[-2, 3, 6, 1, -3, -1, -2, 4] 여기서 이전값에 현재값을 더하면서 배열을 돌면

[-2, 1, 7, 8, 5, 4, 2, 8] 이렇게 된다.

여기서 가장큰값(8)에서 가장 작은 값(-2)을 빼면 답이 된다.

 

---

다른 풀이

def solution(sequence):
    s1 = [s if i % 2 else -s for i, s in enumerate(sequence)]
    s2 = list(map(lambda x: -x, s1))
    dp1, dp2 = [s1[0]], [s2[0]]

    for i in range(1, len(s1)):
        dp1.append(max(s1[i], dp1[i-1] + s1[i]))
        dp2.append(max(s2[i], dp2[i-1] + s2[i]))

    return max(max(dp1), max(dp2))

이거는 DP 스럽게 풀어본 것인데 사실 맨 위의 풀이방법과 같다고 볼 수 있다.

맨 위의 코드 풀이를 보면 이해하기 쉬울 것이다.