[Codility] 5. MinAvgTwoSlice

문제 링크

MinAvgTwoSlice

문제 요약

길이가 N이고 정수로 이루어진 배열 A와 범위가 0<=P<Q<N인 쌍(P,Q)가 주어지면 A[P] + A[P+1] + ... + A[Q]의 산술 평균을 구할 수 있다.
A에서 가장 작은 평균을 갖는 범위의 시작 위치(P)를 구하라.

요구사항

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]

코드

두시간동안 진짜 이해 못해서 구글링했다..
참고링크

• a<=b 일 때, a와 b의 평균은 a 이상이 된다.
• (단, a = b 라면, a와 b의 평균은 a or 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개인 그룹의 경우를 확인해야 하지만,
  문제의 주어진 조건(P<Q, not P<=Q)에 의하면 그룹의 원소는 최소 2개 이상이므로 2개와 3개인 그룹만 비교하면 된다.

public func solution(_ A : inout [Int]) -> Int {
    var minAvg: Double = 0.0
    var minIdx = Int()
    var flagVal: Double = 0.0

    minAvg = Double(A[0] + A[1]) / 2.0
    for i in 2..<A.count {
        flagVal = Double(A[i-2]+A[i-1]+A[i]) / 3.0
        if(minAvg > flagVal) {
            minAvg = flagVal
            minIdx = i-2
        }

        flagVal = Double(A[i-1] + A[i]) / 2.0
        if(minAvg > flagVal) {
            minAvg = flagVal
            minIdx = i-1
        }
    }

    return minIdx
}