프로그래머스 <연속 펄스 부분 수열의 합>

프로그래머스 <연속 펄스 부분 수열의 합>

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

프로그래머스

---

연속 펄스 부분 수열의 합

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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개 사용하는데 1부터 시작하는 펄스 수열을 sequence에 곱한 plus와 -1부터 시작하는 펄스 수열을 sequence에 곱한 minus 수열 2개를 사용한다.

 

plus 수열에서 연속 합 중 가장 큰 것과 minus 수열에서 연속 합 중 가장 큰 것 중 더 큰 값을 정답으로 하면 된다.

 

각각 수열에서 연속 합 중 가장 큰 것을 찾는 방법은 이분 탐색을 사용했다.

이분 탐색으로 나눌 수 있는 경우의 수는 다음과 같다.

1. 가장 큰 것이 왼쪽에 있는 경우
2. 가장 큰 것이 오른쪽에 있는 경우
3. 왼쪽과 오른쪽에 걸쳐 있는 경우

이 3가지 경우 중 큰 값을 구하면 된다.

---

코드

def solution(sequence):
    N = len(sequence)
    plus = [sequence[i] for i in range(N)]
    minus = [sequence[i] for i in range(N)]
    
    p = 1
    m = -1
    for i in range(N):
        plus[i] *= p
        minus[i] *= m
        p *= -1
        m *= -1
    answer = BS(0, N-1, plus)
    answer = max(answer, BS(0, N-1, minus))
    return answer
def BS(left, right, sequence):
    if left == right: return sequence[left]
    mid = (left + right) // 2
    l = BS(left, mid, sequence)
    r = BS(mid+1, right, sequence)
    
    l_part = -int(1e9)
    temp = 0
    for i in range(mid, left-1, -1):
        temp += sequence[i]
        l_part = max(l_part, temp)
    r_part = -int(1e9)
    temp = 0
    for i in range(mid+1, right+1):
        temp += sequence[i]
        r_part = max(r_part, temp)
    return max(l, r, l_part + r_part)

---

결과

---