Codility – TapeEquilibrium

문제

https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/


정답

def solution(A):
    sum_array = [0] * len(A)
    for index,a in enumerate(A):
        if index == 0:
            sum_array[index] = a
        else:
            sum_array[index] = \
                sum_array[index-1] + a

    max_difference = 9223372036854775807
    for index in range(len(A) - 1):
        temp = \
            sum_array[-1] - (2 * sum_array[index])

        if temp < 0: temp *= -1
        if temp < max_difference: max_difference = temp

    return max_difference

풀이

구간합 알고리즘을 사용할 수 있는지 확인하는 문제입니다.

구간합 알고리즘은 각 시점의 구간합을 매번 계산하는 것이 아니라, 특정 배열에 해당 구간의 합이 어떻게 되는지 미리 저장 합니다. 따라서 O(N^2)에서 O(N)으로 시간복잡도가 개선됩니다.

처음 for문에서 구간합을 미리 배열에 저장 합니다.

max_difference를 int 최대 값으로 지정 합니다.

두번 째 for문이 len(A) - 1인 이유는 배열의 마지막 값까지 빼는 경우는 포함되지 않기 때문입니다. 0 < P < N

배열의 값을 모두 더한 sum_array[-1]에서 해당 구간의 sum_array[index]를 두번 빼줍니다. 이미 sum_array[-1]에 해당 구간합이 더해져 있기 때문에, 두번을 빼야, 전체에서 해당 구간의 합을 뺄 수 있기 때문입니다.

절대값이기 때문에 음수의 경우 temp *= -1를 취해 줍니다.


  • 구간합 알고리즘은 적용되는 문제가 많기 때문에 꼭 숙지해야 합니다.
  • 끝 값에 해당 하는 예외상황을 잘 처리해야 합니다.
  • 문제의 조건을 잘 읽어야 합니다. 0 < P < N

Post Author: Jinn