[Swift 알고리즘] MinAvgTwoSlice - Codility

MinAvgTwoSlice coding task - Learn to Code - Codility

---

문제 분석

N개의 정수로 이루어진 배열 A
슬라이스 -> A[P...Q] 범위를 잘라서 평균을 구하는 것을 말함
A를 슬라이스 해서 가장 최소값을 얻도록 하는, P를 return
O(N^2)으로 모든 경우의 수를 따지면 쉽지만, N = 100,000이므로 시간 초과
이것저것 해봤지만 방법이 쉽게 떠오르지 않음 ...

구글링

평균값의 성질을 이용하는 문제라고 한다
1. 두 수의 평균을 구하면, 작은 수 < 평균 < 큰 수
2. 두 그룹의 평균를 구하면, 작은 그룹의 평균 < 전체 평균 < 큰 그룹의 평균
3. 따라서 작은 그룹의 평균이 최솟값이라면, 그것을 포함한 모든 그룹의 평균보다 작다.
4. 작은 그룹은? 원소가 2개인 경우 / 3개인 경우만 따지면 된다. (4개는 2개 * 2로 나눌 수 있다.)

의사코드

minIdx: 정답으로 return할 최소 인덱스
minAvg: minIdx의 판단 기준이 되는 최소 평균값
minIdx를 0으로, minAvg와 최초 2개 원소의 평균값으로 초기화 한다.

for 문으로 2부터 A의 길이만큼 탐색한다
    3개의 평균을 구한다
        i-2, i-1, i의 평균을 구하고, 최소값인지 판단한다
        맞다면, minAvg, minIdx를 갱신한다.
    2개의 평균을 구한다
        i-1, i의 평균을 구하고, 최소값인지 판단한다
        맞다면, minAvg, minIdx를 갱신한다.
    순서는 중요하지 않다.
minIdx를 return한다.

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var minIdx = 0
    var minAvg = (Double(A[0]) + Double(A[1])) / 2

    for i in 2..<A.count {
        let tmpAvgInThree = (Double(A[i-2]) + Double(A[i-1]) + Double(A[i])) / 3
        if minAvg > tmpAvgInThree {
            minAvg = tmpAvgInThree
            minIdx = i - 2
        }

        let tmpAvgInTwo = (Double(A[i-1]) + Double(A[i])) / 2
        if minAvg > tmpAvgInTwo {
            minAvg = tmpAvgInTwo
            minIdx = i - 1
        }
    }

    return minIdx
}

참고

https://nukeguys.tistory.com/175