[프로그래머스] LV. 3. 연속 펄스 부분 수열의 합 - [Python]

 

프로그래머스

문제설명

 

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

 

---

아이디어

부분수열 관련 문제는 accumulate()를 사용하면 편하게 풀릴수 있다고 했는데 이 문제가 바로 그 문제이다.

 

일단 pulse와 repulse를 [1,-1,1,-1 ...]*sequence , [-1,1,-1,1...]*sequence로 설정하고

각각의 부분수열의 합을 계산하여 최댓값을 출력하는 것이다.

 

accumulate(pulse, lambda x, y:max(y,x+y))

 

코드를 보다보면 이 코드가 나오는데, 하나씩 뜯어보면 금방 이해가 될 것이다.

그럼에도 모르겠다면 댓글 달아주세요.

(시작값과 그 다음까지 더한 값을 기준으로 최댓값만 센다는 아이디어.. 이것이 힌트입니다.)

---

코드

from itertools import accumulate

def solution(sequence):
    n = len(sequence)
    pulse = [((-1)**(i%2))*sequence[i] for i in range(n)]
    repulse = [i*(-1) for i in pulse]
    print(pulse)
    print(repulse)
    arr = []
    arr.append(list(accumulate(pulse, lambda x, y:max(y,x+y))))
    arr.append(list(accumulate(repulse, lambda x, y:max(y, x+y))))
    print(arr)
    
    answer = max(max(arr[0]), max(arr[1]))
    return answer