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

알면 풀고 모르면 못 풂

조건파악

 부분수열의 합에 추가로 펄스라는 조건이 추가되었다. 다행스럽게도 펄스는 1과-1뿐이며 어떤 수가 1 또는 -1로 정해지면 이웃한 원소의 펄스는 서로 반대의 펄스로 정해지게 된다. 즉 연속 부분수열의 길이와 별개로 펄스는 두 가지의 경우만 있다. 홀수 인덱스의 원소가 1이고 짝수 인덱스의 원소가 -1이거나 그 반대의 경우이다.

접근

해당 문제는 두 개의 부분 문제로 나눌 수 있다.

 

1. 홀수 인덱스 혹은 짝수 인덱스의 원소에 -1을 곱한 배열을 구하라

2. 부분수열의 합이 최대가 될 때 그 값을 구하라

 

 1번의 경우 입력으로 주어진 배열을 통해 두 개의 배열을 만들어낼 수 있다. 그리고 나면 부분수열의 합이 최대가 될 때 그 값을 구하면 된다. 연속 부분 수열의 합의 최대값을 구하는 알고리즘은 여러 방법이 있다. 그 중 아주 좋은 방법을 알아내서 써먹어 봤다.

 

부분 수열의 합의 최대값 구하기

 소개할 알고리즘은 누적합 기교를 이용한 방법이다. 이곳에서 소개된 것을 참고하였다. 그 방법은 다음과 같다.

 

어떤 배열이 있을 때 f(i)를 해당 배열의 i 번째 인덱스를 끝점으로 하는 음수가 되지 않는 부분 수열의 합이라고 하자. 이때 f(i)는 다음과 같이 정의할 수 있다.

 

부분 수열의 합

 식을 보면 f(i)는 누적합처럼 보인다. 그러나 max()를 통해 선택적으로 누산할 원소를 누락하고 다음 인덱스를 탐색한다. 누락하는 조건은 누적합이 0보다 작을 때, 즉 음수가 될 때이다. 이때 누적을 중단하고 다음 인덱스부터 새롭게 누적을 시작한다.

 

 누적합에 이와 같은 조건을 추가한 이유는 누적합의 최대를 구하기 위함이다. 이전 인덱스까지의 누적합이 음수이면 더하지 않는 게 최대값을 구하는 누적합이기 때문이다. 반대로 누적합이 0보다 크다면 부분수열의 합이 최대가 되는 부분수열은 그 누적합을 포함하게 된다.

 

 그 결과 일부 f(i)는 일종의 구역별 local maximum을 나타내게 된다. f(i)에서 최대값을 찾으면 그것이 global maximum이 될 것이다.

 

의사코드

sequence를 펄스에 따라 두 가지 경우로 나누어 두 개의 배열을 만든다.

각 배열에 대해 부분수열의 합의 최대값을 구한다.

두 값 중 더 큰 것을 고른다.

 

구현

def solution(sequence) :
    
    def pulse(arr) :
        s1,s2 = [], []
        pulse = 1
        for i in sequence :
            s1.append(pulse*i)
            pulse *= -1
            s2.append(pulse*i)    
        return [s1,s2]
    
    def max_prefix(arr) :
        prefix = [0]
        for i in arr:
            prefix.append(max(0, prefix[-1]) + i)
        return max(prefix)
    
    s1,s2 = pulse(sequence)
    answer = max(max_prefix(s1), max_prefix(s2))
    return answer