codility 3-3. TapeEquilibrium

|

문제출처

문제

A non-empty zero-indexed array A consisting of N integers is given.
Array A represents numbers on a tape.
Any integer P, such that 0 < P < N,
splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
In other words, it is the absolute difference between
the sum of the first part and the sum of the second part.

For example, consider array A such that:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7

Write a function: def solution(A)
that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.
For example, given:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

the function should return 1, as explained above.

Assume that:
N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N),
beyond input storage (not counting the storage required for input arguments).

풀이코드

  • Detected time complexity: O(N * N)
  • list slice 후, sum() 을 통해서 합계를 구하는 부분이 O(N^2)의 시간 복잡도를 가진다.
def solution(A):
    li = []
    for P in range(1,len(A)):
        sum1 = sum(A[:P]) # O(N^2)
        sum2 = sum(A[P:])
        diff = sum1 - sum2 if sum1 >= sum2 else sum2 - sum1
        li.append(diff)
    return min(li)

다른사람 풀이

  • Detected time complexity: O(N)
  • abs() 내장 함수를 통해서 숫자의 절대값을 구할 수 있다. abs(-3) » 3, abs(1,2) » 1.2
  • list slice를 사용하지 않는다.
  • min_difference 변수에 None을 담아서 시작한다.
def solution(A):
    sum_of_part_one = 0
    sum_of_part_two = sum(A)
    min_difference = None

    for i in range(1, len(A)):
        sum_of_part_one += A[i-1]
        sum_of_part_two -= A[i-1]
        difference = abs(sum_of_part_one - sum_of_part_two)

        if min_difference == None:
            min_difference = difference
        else:
            min_difference = min(min_difference, difference)

    return min_difference