Table of contents

코딜리티 MinAvgTwoSlice

배열의 모든 조합(P부터 Q까지, 0 <= P < Q)의 평균값에 대해서 최소 평균값을 갖는 P를 찾는 문제이다.

첫번째 풀이

O(N^2)

public int solution(int[] A) {
    int minIndex = A.length;
    double minAvg = Integer.MAX_VALUE;
    for (int i = 0; i < A.length; i++) {
        int sum = A[i];

        for (int j = i - 1; j >= 0; j--) {
            sum += A[j];
            double avg = (double) sum / (i - j + 1);
            if (avg < minAvg) {
                minAvg = avg;
                minIndex = j;
            }
        }
    }
    return minIndex;
}

일단 무식한 방법으로 풀어봤는데, 당연히 time out에 걸릴 줄 알았고, 코드도 딱히 설명할 필요가 없으므로 패스하자.

두번째 풀이

구간 합에 분류되어 있길래 응용할 수 있는 방법을 생각해봤는데 도저히 생각나질 않는다. 결국 이번 문제도 구글의 힘을 빌렸다.

참고. 이 포스팅을 작성하신 분이 가장 이해하기 쉽게 설명해주신것 같다.

  • a <= b일 때, a와 b의 평균은 a 이상이 된다. (a = b 일 때, a와 b의 평균은 a, 즉 두 수가 같은 경우는 a 혹은 b가 된다)
  • 마찬가지로, (a + b) <= (c + d)일 때, (a, b)와 (c, d)의 평균은 (a + b) 이상이 된다.
  • 결국, 원소가 4개(a, b, c, d)인 그룹은 (a, b)와 (c, d)를 나누었을 때, 각각의 평균의 작은 값 이상이 된다.
    • 2개인 그룹이 작은 값이 되므로 4개의 그룹은 고려할 필요가 없어진다.
  • 예외로 원소가 3개인 그룹에서 2개인 그룹과 1개인 그룹의 경우를 확인해야 하지만, 문제에서 주어진 조건에 의하면 그룹의 원소는 최소 2개 이상이므로 2개와 3개인 그룹만 비교한다.

O(N)

private int minAvgTwoSlice2(int[] A) {
    float minAvg = (A[0] + A[1]) / 2f;
    int minIndex = 0;
    for (int i = 2; i < A.length; i++) {
        float avg = (A[i - 2] + A[i - 1] + A[i]) / 3f;
        if (minAvg > avg) {
            minAvg = avg;
            minIndex = i - 2;
        }

        avg = (A[i - 1] + A[i]) / 2f;
        if (minAvg > avg) {
            minAvg = avg;
            minIndex = i - 1;
        }
    }
    return minIndex;
}

첫 2개 요소의 평균을 최소평균으로 정한 뒤, 이후 발생할 수 있는 모든 그룹(원소가 2개 혹은 3개인)에서 최소평균값을 구하여 P에 해당하는 인덱스를 반한한다.

정리

이번 문제는 수학을 아는 사람에겐 쉬운 문제라고 한다. 많은 사람들이 이런 문제에 대해 부정적인 것 같다.