Codility - MinAvgTwoSlice

첫 번째 풀이

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    var sumArray = [Int]()
    var minAvg: Double = 100000
    var minIndex = -1

    sumArray.append(A[0])
    for i in 1..<A.count {
        sumArray.append(sumArray[i-1] + A[i])
    }

    for i in 0..<sumArray.count-1 {
        for j in i+1..<sumArray.count {
            let currValue = sumArray[j] - (i != 0 ? sumArray[i-1] : 0)
            let currAvg: Double = Double(currValue) / Double(j-i+1)
            if currAvg < minAvg {
                minAvg = currAvg
                minIndex = i
            }
        }
    }

    return minIndex
}

시간 복잡도가 O(n^2)라 퍼포먼스 테스트에서 타임아웃 에러가 떴다. 당연히 퍼포먼스 테스트에서 걸러질 줄은 알았는데 이번에도 도저히 효율적인 답이 생각나지 않았다.

최종 풀이

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    var minAvg: Double = Double(A[0] + A[1]) / 2
    var minIndex = 0

    for i in 2..<A.count {
        var currAvg = Double(A[i-2] + A[i-1] + A[i]) / 3
        if currAvg < minAvg {
            minAvg = currAvg
            minIndex = i-2
        }
        currAvg = Double(A[i-1] + A[i]) / 2
        if currAvg < minAvg {
            minAvg = currAvg
            minIndex = i-1
        }
    }

    return minIndex
}

이 문제 역시 구글링을 통해 해결했다.

두 수의 평균은 항상 두 수 중 작은 수보다 크다는 아이디어를 이용하면 2개 원소의 평균을 구하는 경우와 3개 원소의 평균을 구하는 경우만 각각 계산해주면 O(n)으로 문제를 풀 수 있다.

Prefix Sums에 있는 문제들이 대부분 수학적인 아이디어를 생각해서 풀어야 하는 것 같다. 공부 열심히 하자..😂

참고 링크

• https://nukeguys.tistory.com/175