Codility lesson3 - TapeEquilibrium

아무 생각없이 시간복잡도 O(N^2)으로 짰다가 효율성에서 실패.

O(N)으로 개선하여 성공했다.

 

첫 번째 원소를 기준으로 나눈 두 배열의 초기 합을 각각 구한 뒤

구분선을 한 칸씩 옮겨주면서 한 쪽은 초기값에서 숫자를 빼고, 한 쪽은 초기값에 숫자를 더해주면서 그 둘의 절댓값의 차이를 계속 확인해주면 된다.

 

 

 

개선 전

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int answer = -1;
        int n = A.length;

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

            for (int j=0; j<i; j++) {
                sumOfFirstArr += A[j];
            }
            for (int j=i; j<n; j++) {
                sumOfSecondArr += A[j];
            }
            
            int abs = Math.abs(sumOfFirstArr - sumOfSecondArr);
            if (answer<0 || answer > abs) {
                answer = abs;
            }
        }

        return answer;
    }
}

https://app.codility.com/demo/results/trainingU3ZXQ7-3RK/

 

 

 

 

개선 후

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int n = A.length;

        int leftSum = A[0];
        int rightSum = 0;
        for (int i=1; i<n; i++) {
            rightSum += A[i];
        }
        int abs = Math.abs(leftSum-rightSum);

        if (n<=2) {
            return abs;
        }

        for (int i=2; i<n; i++) {
            leftSum += A[i-1];
            rightSum -= A[i-1];
            int tmp = Math.abs(leftSum-rightSum);
            
            if (abs > tmp) {
                abs = tmp;
            }
        }

        return abs;
    }
}

https://app.codility.com/demo/results/trainingSZZAJM-GTY/