[Codility] TapeEquilibrium

0. 문제

비어있지 않은 리스트 A에 N개의 숫자가 있다.(N은 2와 100,000 사이의 숫자)

그리고 0 < P < N 의 조건을 가지는 자연수 P가 있다.

자연수 P에 의해 리스트 A는 이렇게 둘로 나눠지게 된다.

A[0], A[1], ..., A[P − 1]

A[P], A[P + 1], ..., A[N − 1]

이때 |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])| 의 가장 작은 값을 구하라.

1. 답변

처음에 답변은 다 맞췄으나 TimeoutError가 났다.

for p in range(1, len(A)):
     diff = abs(sum(A[:p]) - sum(A[p:]))

위와 같이 간지나게 풀었는데...

루프를 돌 때마다 리스트 A의 합을 구하는 건 너무 멍청했다.

이번 기회로 sum()이 꽤 많은 시간을 차지할 수도 있다는 걸 알았다.

어쨌든 아래처럼 고쳤더니 무난히 통과!

def solution(A):
    left_sum = A[0]
    right_sum = sum(A[1:])
    min_diff = abs(left_sum - right_sum)
    for i in range(1, len(A)-1):
        left_sum += A[i]
        right_sum -= A[i]
        if abs(left_sum - right_sum) < min_diff:
            min_diff = abs(left_sum - right_sum)
    return min_diff

더하기 1번과 N번의 차이..

최종 시간복잡도는 O(N)이 나왔다.