# 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.

라는 문제인데.. 예제로 보면 아래와 같다.

A = { 3 ,4 ,5 ,7} 이라고 하면, P는 1~3까지이며 P가 1일 때 first part는 A[0] 이고 second part 는 A[1] + A[2] + A[3] 이다. 그 다음 각 part 간의 합을 구해 이 합을 서로 빼주는거다. 

우선 생각난 방법은, P를 기준으로 나누어지는 양 구간의 합을 구하는 과정을 P의 범위만큼 반복한다. 이 때 문제에 나와있는 식을 보면 중첩되는 계산들이 있다. 그래서 이 부분을 감안해야 한다. P라는 기준위치가 움직일 때 마다 각 part의 합을 구할 때 중복되는 원소가 생긴다. 

따라서, P=1일 때 각 part 의 합을 구한 뒤, P가 증가하면서 그에 맞게 first part는 1개의 원소를 하나씩 누적하면 되고, 반대로 second part는 원소 1개씩 빠지는거니 누적값에서 해당 원소를 빼준다. 

코드로 정리하면 아래와 같다. 일단 O(N)만큼의 시간이 소모된다. 더 빠른 방법이 없는지.. 궁금하네.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

int solution(vector<int> &A){ int arrSize = A.size(); int firstSum = 0, secondSum = 0; int min = 0; int P = 1; int right = 0; for(;right < P; right++) firstSum += A[right]; for(int idx = P; idx < arrSize; idx++) secondSum += A[idx]; min = abs(firstSum - secondSum); while(++P < arrSize){ firstSum += A[right++]; secondSum -= A[P - 1]; int sum = abs(firstSum - secondSum); if(min > sum) min = sum; } return min; }