어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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 함수를 완성해주세요.
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, ...]와 같은 펄스 수열과 원래 수열이랑 곱해서 더하는 부분을 상당히 깔끔하게 처리할 수 있다.
현재의 pulse를 1로 하고, 현재 sequence의 수에 각각 pulse
와 -pulse
를 곱해준다. 그 사이에 여러개의 로직을 처리하고, 반복 마지막에 pulse *= -1
을 해서 pulse를 전환해준다.
그렇게 되면 나처럼 안하고 더 짧은 코드로 1로 시작하는 펄스 파동과 -1로 시작하는 펄스 파동을 만들어낼 수 있다.
이렇게 해서 s1과 s2라는 리스트를 만들어낸다. (각 수에 1 또는 -1을 곱한 수로 이루어진 리스트이다)
s1과 s2에 대해서 본격적인 핵심 로직에 들어가는데, 핵심 로직은 다음과 같다.
prefix
라는 리스트를 선언한다. 처음에는 당연히 합이 없으므로 prefix = [0]
으로 초기화한다.여기서 핵심아이디어가 나왔다. 즉, 최근 누적합이 음수라면, 그냥 싹다 버리고 0부터 다시 쌓아가자는 것이다.
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))