(코딜리티) Lesson 3 : TapeEquilibrium - Python

처음에는 역시 효율성문제로 100%를 못했다가, 수학적으로 접근해서 문제를 풀었습니다.

 

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

TapeEquilibrium coding task - Learn to Code - Codility

문제설명

예를 들어, 비어있지 않은 배열 A인 [3, 1, 2, 4, 3]이 주어졌을 때,

 

P=1 라면, |(3) - (1+2+4+3)| = 7

P=2 라면, |(3+1) - (2+4+3)| = 5

P=3 라면, |(3+1+2) - (4+3)| = 1

P=4 라면, |(3+1+2+4) - (3)| = 7

 

이때, P는 0<P<N의 값을 가지며, N은 A배열의 길이 입니다.

위 4개의 결과중 최솟값인 1을 return하면 됩니다.

제한 사항

N은 2~100,000사이의 값을 가집니다.

A의 각 요소는 -1000~1000사이의 값을 가집니다.

코드

def solution(A):
    
    s = sum(A)
    b = 0
    m = float('inf')
    for i in A[:-1]:
        b += i
        S = abs(s-b*2)

        if m > S :
            m = S

    return m

해설

만약 A가 [a, b, c, d, e]로 주어진다면, 각 P마다 값은

 

P=1 라면, |(a) - (b+c+d+e)|  -> |(a+b+c+d+e) - 2(a)|

P=2 라면, |(a+b) - (c+d+e)|  -> |(a+b+c+d+e) - 2(a+b)|

P=3 라면, |(a+b+c) - (d+e)|  -> |(a+b+c+d+e) - 2(a+b+c)|

P=4 라면, |(a+b+c+d) - (e)|  -> |(a+b+c+d+e) - 2(a+b+c+d)|

입니다. 

 

이것은 A의 전체 합(a+b+c+d+e)에서 P별로 좌측이든 우측에 2를 곱한 후 빼고 절댓값을 씌우면 됩니다.