[프로그래머스/Lv3] 연속 펄스 부분 수열의 합 (Python)

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

프로그래머스

 

Status : Solved

 

Time : 00:48:37

 

---

 

문제 설명

 

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

 

 

---

 

풀이

 

언제나 DP문제는 나를 겸손하게 만든다. ㅠㅠ

 

몇 가지를 생각해 보자.

 

1. 펄스 수열의 모든 경우의 수를 따지지 말고, 우선 인덱스가 0일 때부터 1, -1, 1...인 펄스 수열을 전부 곱한 새로운 수열을 만들자. 여기서 부분 수열의 합을 구하여, 최솟값과 최댓값을 구한다. 그리고 그 최솟값과 최댓값의 절댓값 중 제일 큰 값이 정답이 된다. (절댓값을 취함으로써 펄스 수열의 방향을 뒤집는 것과 같은 효과를 낼 수 있다)

 

2. 1번에 따라 이 문제는 연속 부분 수열의 합 중 최대와 최소를 구하는 문제가 되었다. 하지만 sequence의 최대 길이는 500,000이다. 부분 수열을 완전탐색하려면 O(N^2)이 되므로, 시간 초과를 피할 수 없다. 따라서 DP를 적용해야 한다.

 

DP[i] 를 sequence의 i번째 원소를 반드시 마지막으로 포함할 때의 모든 연속 부분 수열 중 최솟값과 최댓값이라 가정하자. 그렇다면,

• 최솟값인 DP[i][0]은 현재 sequence값인 sequence[i]와, i-1번째의 최솟값 DP[i-1][0]에 sequence[i]를 더한 값 중 더 작은 값이 된다. 연속 수열이므로 바로 이전의 값만을 참조하면 된다.
• 최댓값인 DP[i][1]은 현재 sequence값인 sequence[i]와, i-1번째의 최댓값 DP[i-1][1]에 sequence[i]를 더한 값 중 더 큰 값이 된다.

 

따라서,

 

DP[i][0]  = min(sequence[i], sequence[i] + DP[i-1][0])

DP[i][1] = max(sequence[i], sequence[i] + DP[i-1][1])

 

로 나타낼 수 있게 된다!

 

이는 O(N)의 시간복잡도로 해결 가능하며, 또한 위 과정에서의 모든 DP의 최댓값과 최솟값을 구한 후 이들의 절댓값의 최댓값을 구하면 정답이 도출된다.

 

 

풀이 코드

def solution(sequence):
    length = len(sequence)
    pulse = lambda x : 1 if x % 2 else -1
    sequence = [ pulse(idx) * sequence[idx] for idx in range(length) ]
    
    dp = [[0, 0] for _ in range(length)]
    dp[0] = [sequence[0], sequence[0]]

    for i in range(1, length) :
        num = sequence[i]
        dp[i][0] = min(num, num + dp[i-1][0])
        dp[i][1] = max(num, num + dp[i-1][1])

    min_val = min(map(min, dp))
    max_val = max(map(max, dp))
        
    return max(abs(min_val), abs(max_val))

풀이 완료!

p.s. 사실 배열 저장할 필요 없이, 계속 최댓값과 최솟값을 업데이트해도 된다.