Lesson 3(Time Complexity) - 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].

정수형 N개의 배열 A가 주어지면 A배열의 1번부터 시작하여 해당 인덱스 이전과 해당 인덱스를 포함한 뒤의 값을 계산하여 이전/이후 절대값 차이가 가장 적은 인덱스를 찾는 문제이다.

 

 

 풀이

// you can also use imports, for example:
import java.util.*;

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int min = Integer.MAX_VALUE;
        int preSum = A[0];
        int postSum = 0;

        for(int i=1; i<A.length; i++){
            postSum += A[i];
        }

        for(int i=1; i<A.length; i++){
            if( Math.abs(preSum - postSum) < min ){
                min = Math.abs(preSum - postSum);
            }
            preSum += A[i];
            postSum -= A[i];
        }

        return min;
    }
}

 

1번째 인덱스를 기준으로 이전 합과 이후 합(1번째 인덱스 포함)을 계산한다.

2번째 인덱스 부터는 다시 전체를 구하지 않고 이전 합에 해당 인덱스의 값을 더하고 이후 합에 해당 인덱스 값을 빼서 계산한다.

 

 

 결과

주소 : app.codility.com/demo/results/trainingZUXY6B-8ZD/

 

제출 결과1 

제출 결과2

 

정답율 100%에 반복문 한번으로 시간복잡도도 O(N) 으로 잘 나왔네요.