Min Average Two Slice by Codility

문제는 아래와 같다.

A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).
For example, array A such that:

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

contains the following example slices:
slice (1, 2), whose average is (2 + 2) / 2 = 2;
slice (3, 4), whose average is (5 + 1) / 2 = 3;
slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.
The goal is to find the starting position of a slice whose average is minimal. Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty zero-indexed array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.
For example, given array A such that:
A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8
the function should return 1, as explained above.
Assume that:
N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−10,000..10,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

처음에 이문제를 이렇게 오해해서 아래와 같이 풀었다.

public int solution(int A[]) {

int length = A.length;

if(length < 2) {

return 0;

}

int minIndex = 0;

double lastAverage = 0d;

   for (int i = 0; i < A.length; i++) {

   

    if(i+1 == A.length) {

    break;

    }

   

    int first = A[i];

    int second = A[i+1];

   

    if(first > second) {

    System.out.println("tmpSum : continue");

    continue;

    }

    int tmpSum = 0;

    double average = 0d;

    if(first == second) {

    average = (first+second)/2;

    System.out.println("if average : " + average);

    }

    else {

    int count = 0;

    do {

    tmpSum += first;

    first++;

    count++;

    }

    while(first <= second);

    average = (double)tmpSum/count;

   

    System.out.println("else average : " + average);

    }

    if(lastAverage == 0 || lastAverage > average) {

    lastAverage = average;

    minIndex = i;

    }

   }

   

   return minIndex;

}

어떻게 오해한것이냐면

예를 들어 int A[] = { 4, 2, 2, 5, 1, 5, 8 }; 라고하면

인접한 두개의 원소 사이에서 갯수의 합 / 카운드

다시말해서 3번째 원소 2와 4번째 원소 5는 2+3+4+5 를 해서 4개의 카운트로 나누어 평균값의 제일 작은 index로 오해를 했다. 이노무 영어가 문제다 ㅋㅋㅋ

이제 제대로 다시 풀어봐야겠다. 인접하는 두개의 원소가 아니라, 원소는 몇개가 될 수 있고, 갯수의 값의 합이구먼...

아래와 같이 수정하면 된다. 아래 내용을 잘 분석해 보면, slice가 2개 또는 3개이다. 왜 2, 3개만 적용하면되냐면, 자세한 내용은 http://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/ 를 참고하면 되고, 간단하게 모든 slice는 2개 또는 3개로 나누어 진다는 것이다.

예를 들어 짝수갯수는 2로 나누어 지고, 홀수 갯수는 2로 나누어지고 마지막것이 3개라는 대충 이런개념... 아닌가? 어쨌든 결론은 2,3개의 slice이외에는 할필요가 없다는 것이다.

public int solution2(int A[]) {

int length = A.length;

if (length < 2) {

return -1;

}

if (length == 2) {

return 0;

}

int minIndex = 0;

double minAverage = 10000d;

// System.out.println("minAverage : " + minAverage);

for (int i = 0; i < length - 2; i++) {

double tmpAverage2 = (double) (A[i] + A[i + 1]) / 2;

System.out.println("2 tmpAverage : " + tmpAverage2);

if (tmpAverage2 < minAverage) {

minAverage = tmpAverage2;

minIndex = i;

}

double tmpAverage3 = (double) (A[i] + A[i + 1] + A[i + 2]) / 3;

System.out.println("3 tmpAverage : " + tmpAverage3);

if (tmpAverage3 < minAverage) {

minAverage = tmpAverage3;

minIndex = i;

}

}

return minIndex;

}