[코딜리티] 파이썬 _ TapeEquilibrium

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

TapeEquilibrium coding task - Learn to Code - Codility

문제번역 :

 

N개의 정수로 구성된 비어 있지 않은 배열 A가 제공됩니다.

어레이 A는 테이프의 숫자를 나타냅니다.

0 < P < N과 같은 정수 P는 이 테이프를 비어 있지 않은 두 부분으로 나눕니다.

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])|

즉, 첫 번째 부분의 합과 두 번째 부분의 합 사이의 절대 차이입니다.

 

예를 들어, A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3과 같은 배열 A를 고려하십시오.

이 테이프를 네 곳으로 나눌 수 있습니다.

P = 1, 차이 = |3 − 10| = 7

P = 2, 차이 = |4 − 9| = 5

P = 3, 차이 = |6 − 7| = 1

P = 4, 차이 = |10 − 3| = 7

 

함수 작성:

N 정수의 비어 있지 않은 배열 A가 주어지면 달성할 수 있는 최소 차이를 반환합니다.

예: A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3 함수는 위에서 설명한 대로 1을 반환해야 합니다.

쓰기 다음 가정에 대한 효율적인 알고리즘: N은 [2..100,000] 범위 내의 정수입니다.

배열 A의 각 요소는 [−1,000..1,000] 범위의 정수입니다.

 

 

정답코드 :

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

from collections import deque
def solution(A):
    # write your code in Python 3.6
    n = len(A)
    # 시작, P는 1-> 0 / 1~끝
    l_sum =A[0]
    r_sum = sum(A[1:])
    r_list = deque(A[1:])
    diff = abs(l_sum-r_sum)
    # P가 N-1까지 오른쪽 맨첫번째 원소를 빼고, 왼쪽에 더해준다. 

    for p in range(2,n):
        number = r_list.popleft()
        l_sum += number
        r_sum -= number
        diff = min(diff, abs(l_sum-r_sum))
    
    #print(diff)
    return diff