[Algorithm] MinAvgTwoSlice

[hwangJi-dev]

💬 문제

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

💬 Idea

O(N**2)의 풀이밖에 떠오르지 않아서 혹시나..? 하고 제출해봤지만 역시나 😊😊!!!! O(N)의 풀이여야 효율성 테스트를 통과할 수 있었다. 따라서 O(N)의 풀이를 도출하려 해봤지만 도저히 O(N)의 시간복잡도를 갖는 풀이가 생각나지 않았다. 그래서 다른 블로그를 참고했는데, 평균값의 원리라는 수학 공식을 새로 알게되었다 !!

평균값의 원리

💡 구간의 평균은 부분구간의 평균 중 가장 작은 부분구간의 평균보다 크다.

평균은 어느 두 수가 있을 때 가장 작은 수보다 큰 값을 가진다. 이 원리로 생각해보았을 때, 원소가 4개인 그룹의 평균은 앞 2개, 뒤 2개로 나누어본다면 앞 뒤 중 작은 그룹보다 큰 값을 가질 것이다. 따라서 2개인 그룹들을 고려하면 4개인 그룹은 확인할 필요가 없어진다.

• 짝수개로 쪼개진 배열들은(2개, 4개, 6개, 8개, 10개 ,,,, 등으로 배열을 슬라이싱한 경우) 2개의 부분그룹들로 다시 쪼개질 수 있고
• 홀수개의 부분그룹들은 3개 + 2개 조합의 부분그룹으로 쪼개질 수 있을 것이다.
• 3개도 2개 + 1개로 쪼개질 수 있지만, 문제에서 그룹(==부분구간)은 2개부터 시작이라고 했으므로 3개는 쪼개질 수 없다.

따라서 이 문제를 풀기 위해서 배열을 2개, 3개로만 슬라이싱해서 평균을 구해보면 가장 작은 평균값을 알 수 있고, 최소 시작 인덱스 또한 도출할 수 있다.

💬 풀이

public func solution4(A : inout [Int]) -> Int {
    var minAvgValue: Double = Double(A[0] + A[1]) / 2
    var minIndex = 0
    
    for i in 2..<A.count {
        let avg2: Double = Double(A[i - 1] + A[i]) / 2
        if minAvgValue > avg2 {
            minAvgValue = avg2
            minIndex = i - 1
        }
        
        let avg3: Double = Double(A[i - 2] + A[i - 1] + A[i]) / 3
        if minAvgValue > avg3 {
            minAvgValue = avg3
            minIndex = i - 2
        }
    }
    
    return minIndex
}

시간 복잡도 : O(N)

평가표 : https://app.codility.com/demo/results/training6Y3P9V-3AR/

코딜리티… 참 좋다 😊 

<참고>

https://nukeguys.tistory.com/175