[codility] TapeEquilibrium

Q. 배열의 포지션 N을 1씩 증가하면서 (좌측 합 - 우측 합) 차이가 가장 작은 값을 구하시오.

    (N은 1부터 시작함)

    A = {3,1,2,4,3};

    3 - 10  = 7

    4 - 9   = 5

    6 - 7   = 1

    10 - 3  = 7

A. 1

 

[멍청이 버전] 

루프를 한번만 돌려서 값을 찾아야지 라는 생각에 갇혀서 하다보니 기괴한 방식으로 되었다.

결국은 2번은 돌려야 값을 찾을 수 있게 되었는데... 한번으로 가능하긴 한가..?

 

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int minDiff = 0;
       
        if(A.length > 0){
            int[][] B = new int[A.length - 1][2];
            for(int i = 1 ; i < A.length ; i++){
                if(i == 1){
                    B[i - 1][0] = A[i - 1];
                } else {
                    B[i - 1][0] = B[i - 2][0] + A[i - 1];
                }
               
                if(i == 1){
                    B[B.length - i][1] = B[B.length - i][1] + A[A.length - i];
                } else {
                    B[B.length - i][1] = B[B.length - i + 1][1] + A[A.length - i];
                }               
            }
            minDiff = 100000;
            for(int i = 0 ; i < B.length ; i++){
                minDiff = Math.min(minDiff, Math.abs(B[i][0] - B[i][1]));
            }
        }
        return minDiff;
       
    }
}

 

[일반 버전]

총 합계를 구해서 좌측값을 올려가면서 빼는 방식 

public int solution(int[] A) {

int n = A.length;

int totSum = 0;

int leftSum = 0;

int rightSum = 0;

 

for(int i = 0 ; i < n ; i++){

totSum = totSum + A[i];

}

 

for(int x = 1 ; x < n ; x++){

leftSum = leftSum + A[x - 1];

rightSum = totSum - leftSum;

minDiff = Math.min(minDiff, Math.abs(leftSum - rightSum));

}

return minDiff;

}