[프로그래머스] 연속 펄스 부분 수열의 합

연속 펄스 부분 수열의 합

프로그래머스

 

• 풀이
  • 나는 최장 연속 부분 수열처럼 투포인터로 하되, 합친 값이 0 이상인 경우까지 2차원으로 구해두고 확인하려함
  • 하지만 이문제는 투포인터 문제가 아님

투포인터의 전제
투포인터(two pointers)는 보통 다음 조건에서 사용됨
1. 구간의 조건이 "단조성(monotonic)"을 가질 때
예: 구간 합이 K 이상이면 오른쪽 포인터를 옮기고, 작으면 왼쪽 포인터를 옮기는 방식.

2. 특정한 조건을 만족하는 구간의 최소 길이, 개수 등을 찾을 때
3. 정렬된 배열, 슬라이딩 윈도우 등에서 성능 최적화를 위해 많이 사용

 

📍 이 문제는 왜 투포인터로 부적합한가?

1. 조건 만족 구간이 단조성을 띄지 않음
펄스 수열이 [1, -1, 1, -1, ...]이나 [-1, 1, -1, 1, ...]로 계속 번갈아 곱해지므로, 인접한 값 간의 부호가 계속 바뀌고, 부분합이 단조 증가/감소하지 않음. 따라서 구간을 늘린다고 해서 좋은 결과가 보장되지 않음.

2. 모든 연속 부분 수열에 대해 최대 합을 찾아야 함
시작점, 끝점이 정해져 있는 구간을 하나하나 보면서 모든 경우를 고려해야 하는 문제. 이는 부분합 최대 구하기 (Kadane's Algorithm) 로 해결하는 게 최적.

3. 구간을 줄이거나 늘려서 정답을 좁히는 방식이 아님
투포인터는 구간을 "조절"하면서 조건을 만족하는 범위를 찾는데, 이 문제는 그런 조건이 아니라, 단순히 모든 연속 구간을 탐색하며 최대값을 찾는 문제

 

def solution(sequence):
    n = len(sequence)
    
    # 펄스 수열을 곱한 결과 2가지
    pulse1 = [sequence[i] * (1 if i % 2 == 0 else -1) for i in range(n)]
    pulse2 = [sequence[i] * (-1 if i % 2 == 0 else 1) for i in range(n)]

    # Kadane's Algorithm
    def max_subarray(arr):
        max_sum = curr_sum = arr[0]
        for num in arr[1:]:
            curr_sum = max(num, curr_sum + num)
            max_sum = max(max_sum, curr_sum)
        return max_sum

    return max(max_subarray(pulse1), max_subarray(pulse2))

 

 

• 다른 사람 풀이

def solution(sequence):
        n = len(sequence)
        plus = [0] * (n + 1)
        minus = [0] * (n + 1)
        
        def find_max(sequence, n, plus, minus):
            answer = -float('inf')
            pulse = 1

            for i in range(1, n + 1):
                now = sequence[i - 1] * pulse
                plus[i] = max(plus[i - 1] + now, now)

                now *= -1
                minus[i] = max(minus[i - 1] + now, now)

                answer = max(plus[i], answer, minus[i])
                pulse *= -1

            return answer
        
        
        return find_max(sequence, n, plus, minus)