처음 코드

import math
def solution(q1, q2):
    nums=q1+q2

    N=len(nums)
    if not sum(nums)%2==0:
        return -1
    target=sum(nums)//2
    
    
    prefix=[0]*N
    for i in range(N):
        prefix[i]=prefix[i-1]+nums[i]
    
    start=0
    end=len(q1)
    answer=math.inf
    while start<=end and 0<=start<N and 0<=end<N:
        cur_sum=0
        if start==0:
            cur_sum=prefix[end]
        else:
            cur_sum=prefix[end]-prefix[start-1]
        if cur_sum>target:
            start+=1
        elif cur_sum<target:
            end+=1
        else:
            # UPDATE
            cost=start+end-len(q1)+1
            answer=min(answer,cost)
            start+=1
    
    if answer==math.inf:
        return -1
    return answer

채점 결과
정확성: 90.0
합계: 90.0 / 100.0

?? 왜지?? 시간 복잡도도 O(N)일텐데…

아!!!!

start=0
end=len(q1)-1 # 여기서 -1을 안써서 틀렸었다

항상 “길이” ↔ “인덱스” 변환시에 -1를 생각하자!!

구간합에서는 [],() 열린구간 닫힌구간 설정을 올바르게 하자!

접근 방법

queue 자료구조 : “FIFO” → 큐 2개를 서로 pop, push하는 연산을 해도 FIFO 성질이 있으므로 “수의 순서”가 유지된다.

그렇다면 주어진 문제를 queue 1에 대한 구간합 문제로 바꾸어 풀 수 있다.

queue 1 “한쪽만 신경” 쓰면 queue 2는 자동으로 결정되기때문.

또한, 구간합에서 prefix를 이용하여 O(N)에 구간합을 구할 수 있도록하였다.