Codility Lesson 05 - MinAvgTwoSlice( JAVA )

https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/

MinAvgTwoSlice coding task - Learn to Code - Codility

 

문제

- N개의 정수들로 이루어진 비어있지 않은 배열 A가 주어진다.

- 0 <= P < Q < N 조건에서 (P, Q)를 A의 부분배열(notice that the slice contains at least two elements : 최소한 2개 이상의 원소들을 가지고 있는 )이라고 할 때, (P, Q)의 평균은 (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1)이다.

- 예시

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

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

- 평균이 최소값 일 때, 시작 위치를 찾아내는 것이 목표이다. 

- 예시에서 최소 평균값은 (1,2)일 때로 return 1을 한다.

 

제한조건

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

N은 2 ~ 100,000 사이의 정수이다.

A의 각 원소들은 -10,000 ~ 10,000 사이의 정수이다.

 

 

풀이

- 평균들과 관련된 수학적 지식이 있어야한다...( 모든 인자를 다 순회하는 것은 timeout이 될께 명백.. )

- 하위의 블로그를 참조하여 문제 풀이시작

https://cheolhojung.github.io/posts/algorithm/Codility-MinAvgTwoSlice.html

[Codility] MinAvgTwoSlice 문제 풀이 | jcheolho

- 요약하자면, (P, Q)는 최소한 2개 이상의 원소를 가지고 있어야 함으로, 2개의 원소를 가진 평균 그룹과 3개의 원소를 가진 그룹들로 나눠서 각 최소값의 평균을 구하면 된다.

- 평균이기에 float로 변수 사용

 

예상 시간복잡도 : O(N) - 최악의 경우 for문을 한번 순회하는 경우

 

소스코드

// 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");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        // 1. 처음 0, 1번 인덱스의 2개 그룹의 평균은 구해놓는다.
        float min_avg = (A[0] + A[1]) / 2f;
        int startPosition = -1;
        for( int i=2; i<A.length; i++ ){
            // 2개 그룹 평균 구하기
            float tmp2avg = (A[i-1] + A[i]) / 2f;
            if( min_avg > tmp2avg ){
                min_avg = tmp2avg;
                startPosition = i-1;
            };

            float tmp3avg = (A[i-2] + A[i-1] + A[i]) / 3f;
            if( min_avg > tmp3avg ){
                min_avg = tmp3avg;
                startPosition = i-2;
            };
        }

        return startPosition;
    }
}