코딜리티 레슨3 Time Complexity 3 - TapeEquilibrium

문제

 

A non-empty 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.

For example, consider array A such that:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7

P = 2, difference = |4 − 9| = 5

P = 3, difference = |6 − 7| = 1

P = 4, difference = |10 − 3| = 7

Write a function: class Solution { public int solution(int[] A); }

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions: N is an integer within the range [2..100,000];

each element of array A is an integer within the range [−1,000..1,000].

Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

​

→ 배열 A에서 P를 기준으로 P 미만의 합에서 P이상의 합을 뺀 결과를 도출

P는 1부터 N까지 순차적으로 들어가며(0<P<N), 도출된 가장작은 값 return

 

답변

 

1. 알고리즘을 풀다보면 수학적 공식을 찾게된다.

2. 알고리즘은 풀수록 실력 느는 다다익선

3. 이번 문제의 공식은 아래와 같다.

4. 요소의 총합에서 pivot 좌측을 뺀 부분이 오른쪽의 총합

5. 공식을 사용하면 반복문은 한 번 사용으로 해결가능하다.(보통 중첩반복문을 사용할 것이라 예상한다. 나도 처음에 떠올린 생각이 그랬으니 😊)

되도록 중첩반복문 사용은 피합시다!

 

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int total = 0;
        
        for(int a : A) total += a;
        
        int min = 0;
        int P = 1;
        int val = 0;
        
        while(P < A.length) {
            val += A[P-1];
            int abs = Math.abs(val - (total-val));
            
            if(min > abs) min = abs;
            else if(P == 1) min = abs;
                        
            P++;
        }
        
        return min;
    }
}

 

결과

 

https://app.codility.com/demo/results/trainingUME9Q2-28P/

 

시간복잡도(Detected time complexity) : O(N)