'Codility'에 해당되는 글 4건

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.

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

가장 간단히 생각할 수 있는 알고리즘은 O(N^2) 으로 이중 for문을 이용해 계산하는 것이다.

그렇게 되면, 문제에서 요구하는 효율적인 알고리즘이 될 수 없기 때문에 이중 for문을 for문 하나와 같은 식으로 분해하는게 이 문제의 핵심이다. 

이 문제에서 요구하는 두 부분의 값에서 공통적으로 이용할 수 있는 것이 무엇인가 했을 때 그 답은 배열 A 원소의 총합이다.

그렇기 때문에 먼저 ∑A[i] 를 구한 후, 하나는 다시 처음부터 구하고 하나는 총합에서 빼는 식으로 별개의 for 문 두개로 분해할 수 있다. 즉, O(N) 의 시간 복잡도로 줄일 수 있다.

추가로, 최초의 minDiff 값은 존재할 수 있는 가장 큰 Diff(100000 * 999 - (-1000) = 100000 * 1000 ) 보다 1을 크게 선언했고 존재할 수 있는 가장 최솟값인 0 이 나올 경우 바로 return 하게 하여 가장 효율적으로 구현해보았다.

유의할점은 두 번째 for 문에서 A.length 까지가 아닌 A.length - 1 까지만 탐색한다는점이다. 그 이유는 P의 범위가 1~N-1 이므로 A[0] 만 왼쪽일 경우부터 A[N-1]만 오른쪽인 경우 까지기 때문이다. (즉, A.length - 2 까지만 빼봐야 한다.)

import java.lang.Math;

class Solution {
    public int solution(int[] A) {
    
        int sumFirst = 0;
        int sumSecond = 0;
        int minDiff = (100000*1000 + 1);
        int tmp;
        
        for(int i = 0; i < A.length; i++){
            sumSecond += A[i];
        }
        
        for(int j = 0; j < A.length - 1; j++){
            sumFirst += A[j];
            sumSecond -= A[j];
            tmp = Math.abs(sumFirst - sumSecond);
            
            if(minDiff > tmp){
                minDiff = tmp;
            }
            
            if(minDiff == 0){
                return minDiff;
            }
        }
        return minDiff;
    }
}