프로그래머스 연속 펄스 부분 수열의 합 (DP)

문제 설명

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

제한 사항

• 1 ≤ sequence의 길이 ≤ 500,000
• -100,000 ≤ sequence의 원소 ≤ 100,000
  • sequence의 원소는 정수입니다.

입출력 예

sequence	result
[2, 3, -6, 1, 3, -1, 2, 4]	10

입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

풀이

• 이거 오늘 풀었던 스티커 모으기 (2) 문제랑 비슷하다. 완전 운으로 풀었네 ㅎㅎㅎ

def solution(sequence):
    answer = 0
    n = len(sequence)
    dp = [0] * n
    dp[0] = sequence[0]
    
    if n == 1:
        return max(dp[0]*-1, dp[0])
    else:
        for i in range(1, n, 2):
            sequence[i] *= -1
        dp[0] = sequence[0]
        for i in range(1, n):
            dp[i] = max(sequence[i], sequence[i] + dp[i-1])
        answer = max(dp)

        for i in range(n):
            sequence[i] *= -1
        dp[0] = sequence[0]
        for i in range(1, n):
            dp[i] = max(sequence[i], sequence[i] + dp[i-1])
        answer = max(answer, max(dp))

    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.00ms, 10.2MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.03ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.2MB)
테스트 6 〉	통과 (0.03ms, 10.2MB)
테스트 7 〉	통과 (0.06ms, 10.1MB)
테스트 8 〉	통과 (0.49ms, 10.3MB)
테스트 9 〉	통과 (0.62ms, 10.2MB)
테스트 10 〉	통과 (5.94ms, 10.4MB)
테스트 11 〉	통과 (7.31ms, 10.7MB)
테스트 12 〉	통과 (74.73ms, 17.7MB)
테스트 13 〉	통과 (93.50ms, 17.7MB)
테스트 14 〉	통과 (79.86ms, 17.4MB)
테스트 15 〉	통과 (68.00ms, 17.7MB)
테스트 16 〉	통과 (64.65ms, 18.9MB)
테스트 17 〉	통과 (404.85ms, 48.2MB)
테스트 18 〉	통과 (389.38ms, 48.6MB)
테스트 19 〉	통과 (412.56ms, 56.1MB)
테스트 20 〉	통과 (344.72ms, 56MB)

• 어... 우와?

def solution(sequence):
    a1, a2 = -111111, -111111
    s1, s2 = 0, 0
    sign = [-1,1]
    for i, s in enumerate(sequence):
        s1 += s * sign[i%2]
        s2 += s * sign[(i+1)%2]
        a1 = max(s1,a1)
        a2 = max(s2,a2)
        s1 = max(0,s1)
        s2 = max(0,s2)
    return max(a1,a2)
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.1MB)
테스트 3 〉	통과 (0.01ms, 10.3MB)
테스트 4 〉	통과 (0.02ms, 10MB)
테스트 5 〉	통과 (0.02ms, 10.3MB)
테스트 6 〉	통과 (0.06ms, 10.3MB)
테스트 7 〉	통과 (0.04ms, 10.3MB)
테스트 8 〉	통과 (0.35ms, 10.3MB)
테스트 9 〉	통과 (0.70ms, 10.1MB)
테스트 10 〉	통과 (3.64ms, 10.3MB)
테스트 11 〉	통과 (6.96ms, 10.4MB)
테스트 12 〉	통과 (70.10ms, 13.9MB)
테스트 13 〉	통과 (71.70ms, 14.1MB)
테스트 14 〉	통과 (70.91ms, 14.2MB)
테스트 15 〉	통과 (72.48ms, 14.1MB)
테스트 16 〉	통과 (71.04ms, 14.1MB)
테스트 17 〉	통과 (352.71ms, 31.3MB)
테스트 18 〉	통과 (348.84ms, 31.2MB)
테스트 19 〉	통과 (344.66ms, 31.6MB)
테스트 20 〉	통과 (341.89ms, 31.8MB)

• 빠름

def solution(sequence):

    # 1 부터 연속펄스 부분 수열을 곱한값 찾기 prefix sum 만들기 
    # maxV - minV 
    # 각각의 리스트에서 max()
    answer = 0
    prefixS = [0]
    for i in range(len(sequence)):
        pulse = 1 if i%2 ==0  else -1
        prefixS.append(prefixS[-1]+pulse*sequence[i])

    return abs(max(prefixS) - min(prefixS))
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.1MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.3MB)
테스트 5 〉	통과 (0.01ms, 10.3MB)
테스트 6 〉	통과 (0.01ms, 10.2MB)
테스트 7 〉	통과 (0.02ms, 10.1MB)
테스트 8 〉	통과 (0.10ms, 10.1MB)
테스트 9 〉	통과 (0.39ms, 10MB)
테스트 10 〉	통과 (1.07ms, 10.5MB)
테스트 11 〉	통과 (2.20ms, 10.6MB)
테스트 12 〉	통과 (23.09ms, 17.8MB)
테스트 13 〉	통과 (22.49ms, 17.8MB)
테스트 14 〉	통과 (24.46ms, 17.8MB)
테스트 15 〉	통과 (24.59ms, 17.7MB)
테스트 16 〉	통과 (22.96ms, 19.1MB)
테스트 17 〉	통과 (112.46ms, 50.3MB)
테스트 18 〉	통과 (116.15ms, 52.2MB)
테스트 19 〉	통과 (118.42ms, 58.6MB)
테스트 20 〉	통과 (134.35ms, 58.7MB)

• 오와... 이렇게도 푸는구나?

def solution(sequence):
    acc_list=[0]
    for idx in range(len(sequence)):
        if idx%2==0:
            acc_list.append(acc_list[-1]+sequence[idx])
        else:
            acc_list.append(acc_list[-1]-sequence[idx])
    return max(acc_list)-min(acc_list)
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	통과 (0.01ms, 10.3MB)
테스트 6 〉	통과 (0.01ms, 10.2MB)
테스트 7 〉	통과 (0.02ms, 10.2MB)
테스트 8 〉	통과 (0.09ms, 10.3MB)
테스트 9 〉	통과 (0.19ms, 10.2MB)
테스트 10 〉	통과 (1.86ms, 10.3MB)
테스트 11 〉	통과 (3.71ms, 10.9MB)
테스트 12 〉	통과 (20.46ms, 17.8MB)
테스트 13 〉	통과 (20.96ms, 17.9MB)
테스트 14 〉	통과 (21.82ms, 17.8MB)
테스트 15 〉	통과 (26.54ms, 17.8MB)
테스트 16 〉	통과 (19.79ms, 19MB)
테스트 17 〉	통과 (107.60ms, 50.4MB)
테스트 18 〉	통과 (104.11ms, 52.3MB)
테스트 19 〉	통과 (112.87ms, 58.8MB)
테스트 20 〉	통과 (111.49ms, 58.8MB)

• 고수들의 기상천외한 방법을 보면서 너무 신기해서 시간 가는 줄 모르겠다.