TapeEquilibrium - (Codility, 시간복잡도)

def solution(A):
    P1 = 0
    P2 = sum(A)
    stack = []

    for i in range(1,len(A)):
        P1 += A[i-1]
        P2 -= A[i-1]
        ans = abs(P1-P2)
        if len(stack) == 0:
            stack.append(ans)
        elif stack[-1] > ans:
            stack.pop()
            stack.append(ans)
    
    return stack[-1]

 

sum의 시간복잡도는 O(n)이기 때문에 반복문에 들어가면 O(n**2)의 시간 복잡도가 나온다.

 

그러니 단순히 sum을 해주고 n-1까지 더하고 빼기를 반복하면 해결된다.