Task )
This is a demo task. You can read about this task and its solutions in this blog post.
A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.
1) Sum a half of left values of the array and a half of the right values of the array separately.2) Go through left side of the array and then go through right side of the array again.When summing up the values use the summed vales on 1).
package yarbonglab.codility.demo;
/**
* Created by yarbong on 23/01/2016.
*/
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
public class Equilibrium {
public static void main(String[] args) {
Equilibrium equilibrium = new Equilibrium();
int[] A = {-1, 3, -4, 5, 1, -6, 2, 1};
int p = equilibrium.solution(A);
System.out.println("The position : " +p);
}
public int solution(int[] A) {
// write your code in Java SE 8
int p = -1;
int n = A.length; // TODO : N <= 100000
int midP = n/2-1;
long sumHalfLeft = sumValues(A, 0, midP, 0);
long sumHalfRight = sumValues(A, midP+1, n , 0);
long sumLeft = sumHalfLeft;
long sumRight = sumHalfRight;
if(sumLeft == sumRight) p = midP;
else p = -1;
int sIdx = 0;
int eIdx = midP-1;
long halfLeft = 0l;
long halfRight = sumHalfRight;
while(p == -1 && sIdx < n) {
for(int t = sIdx; t < eIdx; t++) {
if(t==0) {
sumLeft = 0;
}else {
sumLeft = sumValues(A, sIdx+1, t, halfLeft);
}
if(t == n-1){
sumRight = 0;
}else {
sumRight = sumValues(A, t+1, eIdx , halfRight);
}
if(sumLeft == sumRight) p = t;
if((t+1) == eIdx){
sIdx = eIdx;
eIdx = n;
halfLeft = sumHalfLeft;
halfRight = 0l;
}
}
}
return p;
}
public long sumValues(int[] V, int sIdx, int eIdx, long sumHalf) {
long sum = 0l;
for(int t = sIdx; t < eIdx; t++) {
sum += (long)V[t] + sumHalf;
}
return sum;
}
}
'Dev' 카테고리의 다른 글
책, 토비의 스프링 3.0 "1부 이해" - 기록하고 또 보기 (0) | 2017.07.08 |
---|---|
jQuery Datepicker 랜더링 (0) | 2017.07.06 |
Print multiple values in a row by using ArrayList.subList (0) | 2015.11.18 |
Difference between start and run method in Thread in Java (0) | 2015.08.07 |
Maven Build lifecycle and POM version SNAPSHOT (0) | 2015.02.28 |