오답
from itertools import accumulate
def solution(sequence):
result = []
for flag in [1, -1]:
pulse = []
for i in sequence:
pulse.append(i*flag)
flag *= -1
idx, val = 0, 0
for i, j in enumerate(accumulate(pulse)):
if j > val:
val = j
idx = i
from_left = 0
for i, j in enumerate(accumulate(pulse[:idx+1])):
if val > from_left:
from_left = val
val -= j
result.append(from_left)
return max(result)
어디가 잘못된걸까? 정리해보자.
- 입력 리스트를 받아서 1에서 시작하는 펄스를 곱한 값을
pulse에 저장한다. itertools모듈의accumulate함수를 사용해서 누적 합을 구하고, 그 중 가장 큰 값의 인덱스와 값을 저장한다.- 구한 인덱스까지 다시 누적합을 구하고, 왼쪽에서부터 차례대로 빼며 더 커질 수 있는지 조사한다.
- 결과값을
result리스트에 저장하고, -1에서 시작하는 펄스에 대해 위 과정을 다시 수행한다. - 두 값 중 더 큰 값을 리턴한다.
한번 더 생각해보자. 누적합이 가장 컸을 때보다 더 큰 부분이 존재할 수 있는가? 존재할 수 있는 것 같다. 만약 누적 합이 [ .... 99, ..., 80]이지만 누적합 80에 해당하는 부분이 100이라면, 100 하나가 인덱스 0부터 누적합 99에 해당하는 값까지보다 더 클 것이다. 그럼 위 과정을 반복하면 풀 수 있을까?
2차 시도
from itertools import accumulate
def solution(sequence):
result = []
for flag in [1, -1]:
pulse = []
for i in sequence:
pulse.append(i*flag)
flag *= -1
ls = pulse
while ls:
idx, val = 0, 0
for i, j in enumerate(accumulate(ls)):
if j > val:
val = j
idx = i
from_left = 0
for i, j in enumerate(accumulate(ls[:idx+1])):
if val > from_left:
from_left = val
val -= j
result.append(from_left)
ls = ls[idx+1:]
return max(result)아까보다 더 많이 틀리고 시간초과가 발생한다.
- 인덱스 0부터
n까지의 구간 중, 누적합이 줄어들기 전까지 합을 구하고 왼쪽에서부터 줄여나가 더 커질 수 있는지 조사하여 결과 값에 추가한다. - 그 다음 부분리스트에 대해 반복한다.
3차 시도
from itertools import accumulate
def solution(sequence):
result = []
for flag in [-1]:
pulse = []
for i in sequence:
pulse.append(i*flag)
flag *= -1
ls = list(accumulate(pulse))
while ls:
end, val = 0, 0
for i, j in enumerate(ls):
if j > val:
val = j
end = i
tmp = 0
for i, j in enumerate(ls[:end+1]):
if val - j > val:
tmp = j
result.append(val-tmp)
ls = ls[end+1:]
return max(result)
여전히 시간초과가 많이 난다. 구조적인 개선이 필요하다. DP가 필요하다.
Dynamic Programming
아래는 김태홍 님께 힌트를 얻어 구현한 동적 계획법 풀이이다.
def solution(sequence):
result = []
for flag in [1, -1]:
dp = []
for i in sequence:
dp.append(i*flag)
flag *= -1
for idx in range(1, len(dp)):
dp[idx] = max(dp[idx-1]+dp[idx], dp[idx])
result.append(max(dp))
return max(result)간단하게 풀 수 있었다. DP를 연습중이라 이런 풀이를 알게 되어서 기쁘다. 다만 무엇이 되는지 아는것도 중요하지만 이전에 시도했던 코드들이 왜 안되는지도 알고 싶다.
왜 안될까? - 4차 시도
아래의 코드는 3차 시도를 개선한 코드이다 :
from itertools import accumulate
def solution(sequence):
result = []
for flag in [-1]:
pulse = []
for i in sequence:
pulse.append(i*flag)
flag *= -1
ls = list(accumulate(pulse))
while ls:
end, val = 0, 0
for i, j in enumerate(ls):
if j > val:
val = j
end = i
tmp = val
for i, j in enumerate(ls[:end+1]):
if val - j > tmp:
tmp = val - j
result.append(tmp)
ls = ls[end+1:]
return max(result)정답률이 올라갔지만 여전히 시간초과에 시달리고있다. 한계는 어쩔 수 없지만 논리라도 바로잡고 싶다. 어디가 문제일까?
하루 쉬자
하룻밤 자고나서 다시 생각해보니 위 동적 계획법 코드가 내가 구현하고자 하는 것을 가장 효율적으로 구현하고 있다는 생각이 든다.
다른 코드들
김종도 님의 풀이:
def solution(sequence):
table = [[0 for _ in range(len(sequence) + 1)] for _ in range(2)]
weight = 1
for i in range(len(sequence)):
table[0][i + 1] = table[0][i] + sequence[i] * weight
table[1][i + 1] = table[1][i] - sequence[i] * weight
weight *= -1
return max(max(table[0]) - min(table[0]), max(table[1]) - min(table[1]))이게 어떻게 되는거지? 최대값에서 최소값을 빼면 된다고?
Magenta195님의 풀이:
def solution(sequence):
length = len(sequence)
pulse = lambda x : 1 if x % 2 else -1
sequence = [pulse(idx) * sequence[idx] for idx in range(length)]
dp = [[0, 0] for _ in range(length)]
dp[0] = [sequence[0], sequence[0]]
for i in range(1, length) :
num = sequence[i]
dp[i][0] = min(num, num + dp[i-1][0])
dp[i][1] = max(num, num + dp[i-1][1])
min_val = min(map(min, dp))
max_val = max(map(max, dp))
return max(abs(min_val), abs(max_val))
def st(sequence):
length = len(sequence)
idx, num, answer = 1, abs(sequence[0]), abs(sequence[0])
prev = sequence[0] > 0
while idx < length :
now = sequence[idx] > 0
if sequence[idx] == 0 or prev != now :
num += abs(sequence[idx])
else :
answer = max(answer, num)
num = abs(sequence[idx])
prev = now if sequence[idx] != 0 else not prev
idx += 1
answer = max(answer, num)
return answer1과 -1에서 각각 시작하는 pulse로 sequence를 2번 구하지 않고, min과 max를 사용해 한번에 구했다.
정진효, HeaseoChung님의 풀이:
def solution(sequence):
a1, a2 = -111111, -111111
s1, s2 = 0, 0
sign = [-1,1]
for i, s in enumerate(sequence):
s1 += s * sign[i%2]
s2 += s * sign[(i+1)%2]
a1 = max(s1,a1)
a2 = max(s2,a2)
s1 = max(0,s1)
s2 = max(0,s2)
return max(a1,a2)a에는 누적 최대값을, s에는 음수로 떨어질 경우에는 0, 그렇지 않으면 s를 유지하게 했다.
이찬우 님의 풀이:
import sys
from functools import lru_cache
sys.setrecursionlimit(10000000)
def get_answer_factory(array):
@lru_cache(None)
def get_answer(start, end, is_use):
if start == end:
return 0
return max(0, array[start] + get_answer(start+1, end, True)) if is_use else max(get_answer(start + 1, end, True), get_answer(start + 1, end, False))
return get_answer
def solution(sequence):
get_answer_1 = get_answer_factory(
[val if i % 2 else -val for i, val in enumerate(sequence)],
)
get_answer_2 = get_answer_factory(
[-val if i % 2 else val for i, val in enumerate(sequence)],
)
return max(
get_answer_1(0, len(sequence), True),
get_answer_2(0, len(sequence), True),
get_answer_1(0, len(sequence), False),
get_answer_2(0, len(sequence), False),
)Frank, 박창헌 님의 풀이:
def solution(sequence):
# 1 부터 연속펄스 부분 수열을 곱한값 찾기 prefix sum 만들기
# maxV - minV
# 각각의 리스트에서 max()
answer = 0
prefixS = [0]
for i in range(len(sequence)):
pulse = 1 if i%2 ==0 else -1
prefixS.append(prefixS[-1]+pulse*sequence[i])
return abs(max(prefixS) - min(prefixS))최대값에서 최소값을 빼서 구했다.
waf 님의 풀이:
def solution(sequence):
acc_list=[0]
for idx in range(len(sequence)):
if idx%2 == 0:
acc_list.append(acc_list[-1]+sequence[idx])
else:
acc_list.append(acc_list[-1]-sequence[idx])
return max(acc_list)-min(acc_list)역시 최대값에서 최소값을 빼서 구했다.
레벨이 높아질수록 다양한 코드들이 많이 나오고, 이해하는데 시간이 더 걸리는 것 같다.
이토록 멋진 휴식!