[프로그래머스] 연속 펄스 부분 수열의 합 Lv.3 파이썬

문제 링크

1. 문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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 함수를 완성해주세요.

2. 접근 방식

백준 1912번 연속합(링크) 문제와 상당히 유사합니다. 차이점이라면 주어진 수열을 펄스 '처리' 한 후 부분수열의 최대값을 구하면 됩니다. 유의할 점은 [1,-1,1,-1 ... ], [-1,1,-1,1 ...] 의 두 펄스 수열을 곱했을 때 최대값이 다르게 나온다는 것입니다. 따라서
1. 두 가지 경우의 최대값을 모두 구하거나
2. 한 가지 펄스 수열만 곱한 뒤 최대값과 최소값의 절대값을 비교한다는
두 가지 풀이 방법이 있습니다.

3. 풀이

def solution(sequence):
    pos_seq=[]
    neg_seq=[]
    for i in range(len(sequence)):
        if i%2==1:
            pos_seq.append((-1)*sequence[i]) #[1,-1,1 ..]의 펄스 수열을 곱함
            neg_seq.append(sequence[i]) #[-1,1,-1 ..]의 펄스 수열을 곱함
        else:
            neg_seq.append((-1)*sequence[i])
            pos_seq.append(sequence[i])
    for i in range(1,len(sequence)):
        pos_seq[i]=max(pos_seq[i],pos_seq[i-1]+pos_seq[i])
        neg_seq[i]=max(neg_seq[i],neg_seq[i-1]+neg_seq[i])
    return max(max(pos_seq),max(neg_seq))

저는 두 가지 수열의 최대값을 모두 구했습니다. 사실 어떤 접근 방식으로든 결국 두 가지 연속값의 최대값을 구해 비교하기 때문에 큰 차이는 없습니다. 연속값의 최대값을 구하는 코드는 다음과 같습니다.

def solution(array):
    for i in range(1,len(array)):
        array[i]=max(array[i],array[i-1]+array[i])
    return array

array의 i번째 항은 i-1번째 항까지 구한 연속합의 최대값과 i번째 항을 더했을 때의 값을 비교하여 최대값으로 대체됩니다. 이후 array의 최대값을 구하면 연속합의 최대값을 찾을 수 있습니다.

array=[2,-6,10,-5,7]의 연속합을 찾기 위해 위의 function에 대입했다고 가정합시다. 직관적으로 이 수열의 연속값은 최대 10-5+7=12임을 알 수 있습니다.

1. i=1일때 array[1]은 max(-6,2-6)=-4가 됩니다.
2. i=2일때 array[2]은 max(-4+10,10)=10이 됩니다
3. i=3일때 array[3]은 max(-5,10-5)=5,
4. i=4일때 array[4]=12가 됩니다.
   array=[2,-4,10,5,12]

따라서 이 function을 통해 array는 i번째 항까지 최대 연속합으로 대체됩니다. 배열을 한 번만 탐색해서 누적합을 찾아내는 DP 알고리즘으로 볼 수 있습니다.