MinAvgTwoSlice

🔗 문제 링크

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

❔ 문제 설명

A non-empty 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:

def solution(A)

that, given a non-empty 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.

⚠️ 제한사항

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

---

💡 풀이 (언어 : Java & Python)

갑자기 오늘 막바지 문제부터 난이도가 확올라가는 느낌이다. 이 문제는 전체 케이스를 다 도는 것밖에 생각이 안나서 포기하고 다른 사람들의 풀이를 참고했다. 중요한 핵심 아이디어는 케이스 개수의 상관없이 평균이 가장 작은 케이스가 무조건 들어가는 경우는 2개, 3개 이 두가지 경우만 생각하면 된다. 가장 작은 단위로 쪼갠게 2개이고, 3개는 2개보다 평균이 낮을 케이스가 존재하기 때문이다 (ex. 0 1 0) 반복문을 2개경우, 3개경우 따로 두번 돌아 최소값 케이스의 첫번째 인덱스를 구하면 정답이다.

Java

class Solution {
    public int solution(int[] A) {
        double min = 10000;
        int answer = 0;
        // 두개씩 짝인 경우
        for (int i = 0; i < A.length-1; i++) {
            double check = (double) (A[i] + A[i+1]) / 2;
            if (check < min) {
                min = check;
                answer = i;
            }
        }
        // 세개씩 짝인 경우
        for (int i = 0; i < A.length-2; i++) {
            double check = (double) (A[i] + A[i+1] + A[i+2]) / 3;
            if (check < min) {
                min = check;
                answer = i;
            }
        }
        return answer;
    }
}

Python

def solution(A):
    minimum = (A[0] + A[1]) / 2
    answer = 0
    # 두개씩 Slice
    for i in range(1, len(A)-1):
        twoAverage = (A[i] + A[i+1]) / 2
        if twoAverage < minimum:
            minimum = twoAverage
            answer = i
	# 세개씩 Slice
    for i in range(len(A)-2):
        threeAverage = (A[i] + A[i+1] + A[i+2]) / 3
        if threeAverage < minimum:
            minimum = threeAverage
            answer = i
    
    return answer