문제

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

풀이

나의 풀이

• [1 ,-1, 1, -1, ...] 순서로 반복될 때 누적 합을 저장하며 다음과 같은 정보를 기록하며, queue에다가 하나씩 append해준다.
  • 현재까지의 합 / 현재까지의 최대 합 / 최대 합일 때의 인덱스
• [-1, 1, -1, 1, ...] 순서로 반복될 때도 마찬가지로 다음 정보를 구하며, queue에다가 하나씩 append해준다.
  • 현재까지의 합 / 현재까지의 최대 합 / 최대 합일 때의 인덱스
• 각 queue에 대해서, 처음부터 각 max index까지 슬라이싱해준다. (뒤에는 더 볼 필요 없으므로)
• 다시, 처음부터 누적합을 구해나간다. 그런데, 처음부터(index 0부터) 구해나가는 것이 아니라 맨 끝부터 구해나간다. 그러다가 음수를 만나게 되면, 더 이상 누적합에 포함시키지 않고 바로 반복문 종료. 왜? 누적합에 음수가 들어가는 순간 바로 작아지니까 + 더 살펴본다고 해서 합이 더 커지지도 않으니까. (왜? 우리는 이미 '최대' 인덱스에서 시작했으니 더 이상 최대일 수 없음)
• 그렇게 해서 두 개의 큐에 대해서 누적합을 구한 후, 둘 중 최댓값을 리턴한다.

나의 코드

from collections import deque
def solution(sequence):
    first_queue, second_queue = deque(), deque()
    first_sum, second_sum = 0, 0
    first_maxsum, second_maxsum = 0, 0
    first_maxidx, second_maxidx = 0, 0
    ones = [1, -1]
    
    for i, num in enumerate(sequence):
        if i == 0:
            first_queue.append(num)
            second_queue.append(num * -1)
            first_sum = num
            first_maxsum = num
            second_sum = num * -1
            second_maxsum = num
        else:
            #FIRST_QUEUE
            seq = num * ones[i%2]
            f_newsum = first_sum + seq
            if f_newsum > first_maxsum:
                first_maxidx = i
                first_maxsum = f_newsum
            first_sum += seq
            first_queue.append(seq)
            #SECOND_QUEUE
            seq = num * ones[(i+1)%2]
            s_newsum = second_sum + seq
            if s_newsum > second_maxsum:
                second_maxidx = i
                second_maxsum = s_newsum
            second_sum += seq
            second_queue.append(seq)
    
    #각 큐의 maxidx까지 슬라이싱
    first_queue = list(first_queue)[:first_maxidx+1]
    second_queue = list(second_queue)[:second_maxidx+1]
    first_queue = deque(first_queue)
    second_queue = deque(second_queue)
    
    #각 큐의 max_idx부터 시작해서 거꾸로 가면서 max_sum을 다시 갱신
    fms, sms = 0, 0
    fcur, scur = 0, 0
    for i in range(first_maxidx, -1, -1):
        fcur += first_queue[i]
        if fcur > fms:
            fms = fcur
    for i in range(second_maxidx, -1, -1):
        scur += second_queue[i]
        if scur > sms:
            sms = scur
            
    return max(fms, sms)

까딱했다간 시간 초과 날 뻔한 풀이였다..

더 효율적인 풀이

아이디어는 나와 비슷한데, 이걸 더 효과적으로 하는 방법이 있었다..!!! 충격! 아이디어가 너무 좋았다.

1. 우선 [1, -1, 1, -1, ...]이랑 [-1, 1, -1, 1, ...]와 같은 펄스 수열과 원래 수열이랑 곱해서 더하는 부분을 상당히 깔끔하게 처리할 수 있다.
   현재의 pulse를 1로 하고, 현재 sequence의 수에 각각 pulse와 -pulse를 곱해준다. 그 사이에 여러개의 로직을 처리하고, 반복 마지막에 pulse *= -1을 해서 pulse를 전환해준다.
   그렇게 되면 나처럼 안하고 더 짧은 코드로 1로 시작하는 펄스 파동과 -1로 시작하는 펄스 파동을 만들어낼 수 있다.
   이렇게 해서 s1과 s2라는 리스트를 만들어낸다. (각 수에 1 또는 -1을 곱한 수로 이루어진 리스트이다)

2. s1과 s2에 대해서 본격적인 핵심 로직에 들어가는데, 핵심 로직은 다음과 같다.

   • 누적합을 의미하는 prefix라는 리스트를 선언한다. 처음에는 당연히 합이 없으므로 prefix = [0]으로 초기화한다.
   • s1 또는 s2를 순회하면서 다음과 같은 로직을 수행한다.
     • prefix의 마지막원소(즉, 가장 최근까지 누적된 합)과 0 중에 더 큰 것을 골라서 현재 수와 더한 다음 그것을 prefix에 append한다.

       여기서 핵심아이디어가 나왔다. 즉, 최근 누적합이 음수라면, 그냥 싹다 버리고 0부터 다시 쌓아가자는 것이다.

   • 그렇게 해서 나온 prefix 리스트에서 최댓값을 고른다.
   • s1과 s2에서 나온 최댓값 중에서 최댓값이 바로 정답이다.

코드

def solution(sequence):
    pulse = 1
    s1, s2 = [], []
    for num in sequence:
        s1.append(num * pulse)
        s2.append(num * (-pulse))
        pulse *= -1
    
    #s1에 대해서 누적합
    prefix1 = [0]
    for num in s1:
        prefix1.append(max(0, prefix1[-1]) + num)
    
    #s2에 대해서 누적합
    prefix2 = [0]
    for num in s2:
        prefix2.append(max(0, prefix2[-1]) + num)
    
    return max(max(prefix1), max(prefix2))