[codility] TapeEquilibrium

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

TapeEquilibrium coding task - Learn to Code - Codility

오.. O(n*n)이라 실패

def solution(A):
    # write your code in Python 3.6
    min_sum = max(A)
    for i in range(1,len(A)):
        sum_p_head = sum(A[:i])
        sum_p_tail = sum(A[i:])
        min_sum = min(min_sum, sum_p_head - sum_p_tail if sum_p_head >= sum_p_tail else sum_p_tail - sum_p_head)
    return min_sum

 

O(n)으로 만들었는데 예외 케이스 처리 안해서 실패

def solution(A):
    # write your code in Python 3.6
    min_sum = max(A)
    sum_head = 0
    sum_tail = sum(A)

    for i in range(1,len(A)):
        sum_head += A[i]
        sum_tail -= A[i]
        min_sum = min(min_sum, sum_head - sum_tail if sum_head >= sum_tail else sum_tail - sum_head)
    return min_sum

 

아... len(A)가 2일 때는 따로 해줘야 함

예외케이스 신경쓰자!!!

그리고 for문 범위 잘못됨ㅠㅠ

으... 53프로다ㅠㅠ

def solution(A):
    # write your code in Python 3.6
    if len(A) == 2:
        return abs(A[0] - A[1])
        
    min_sum = sum(A)
    sum_head = 0
    sum_tail = sum(A)

    for i in range(0,len(A)-1):
        sum_head += A[i]
        sum_tail -= A[i]
        min_sum = min(min_sum, sum_head - sum_tail if sum_head >= sum_tail else sum_tail - sum_head)
    return min_sum

 

 

음수일 때 생각해야 하니 min_sum에 절댓값 처리하기

아... 92프로다

def solution(A):
    # write your code in Python 3.6
    if len(A) == 2:
        return abs(A[0] - A[1])
        
    min_sum = abs(sum(A))
    sum_head = 0
    sum_tail = sum(A)

    for i in range(0,len(A)-1):
        sum_head += A[i]
        sum_tail -= A[i]
        min_sum = min(min_sum, abs(sum_head - sum_tail))
        #print(sum_head, sum_tail, min_sum)
    return min_sum

와.... min_sum이 잘못됐네

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

엄청 삽질했다

테스트케이스 작성부터 해보자! 

def solution(A):
    # write your code in Python 3.6
    if len(A) == 2:
        return abs(A[0] - A[1])
        
    min_sum = sum([abs(i) for i in A])
    sum_head = 0
    sum_tail = sum(A)

    for i in range(0,len(A)-1):
        sum_head += A[i]
        sum_tail -= A[i]
        min_sum = min(min_sum, abs(sum_head - sum_tail))
        print(sum_head, sum_tail, min_sum)
    return min_sum