[Swift 알고리즘] Codility - MinAvgTwoSlice

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "Codility - MinAvgTwoSlice" 문제를 풀었습니다.

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

MinAvgTwoSlice coding task - Learn to Code - Codility

 

풀이

이번 문제는 평균이 최소가 되는 구간의 시작 index를 구하는 문제입니다.

이번 문제는 O(N)으로 해결을 해야 하기 때문에

바로 떠오르는 O(N^2) 방법은 시도만 하고 제출은 안 했습니다.

 

그렇다면 어떻게 O(N)으로 해결을 해야하는가?에 대한 고민이 있었는데요.

이전 문제인 구간합을 이용해야 하나? 했지만

이전 문제는 구간이 input으로 주어졌지만 이번 문제는 구간을 직접 구해야 하기 때문에

O(N)으로 적용하기에는 무리가 있어 보였습니다.

 

그래서 결국에는 구글에 도움을 구했고... 평균값의 원리를 이용한 문제였습니다.

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

예를 들어, [1, 2, 3, 4]를 [1, 2], [3, 4]로 부분 구간으로 나누어 평균을 구하면

(1 + 2) / 2 = 1.5, (3 + 4) / 2 = 3.5 입니다.

전체 평균인 (1 + 2 + 3 + 4) / 4 = 2.5는 평균이 작은 부분구간인 [1, 2]의 평균보다 큽니다.

 

위 원리를 이용하면 부분 구간의 평균을 구하면 더 큰 범위의 구간 평균을 구하지 않고도 알 수 있다는 것이죠.

따라서 2개짜리 구간의 합과 3개짜리 구간의 합만 비교하여 최소를 구하면

4개짜리, 5개짜리 등은 구하지 않아도 됩니다.

 

이로서 O(N) 풀이를 할 수 있게 된답니다. (따란) 

 

사담 

문제를 다룬 블로그의 한 후기는 알면 풀고 모르면 못 푸는 그런 문제라네요 ㅎ...

이런 종류의 문제는 참 난감하고 속상합니다. 초등학교 수학부터 다시 해야 하나 싶고... ㅠㅠ

여러 가지로 열심히 해야할 게 많네요.

 

감사합니다!

 

전체 코드

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(A[0] + A[1]) / 2.0
    var result = 0
    for i in 2..<A.count {
        //3개짜리 평균
        let threeAvg = Double(A[i-2] + A[i-1] + A[i]) / 3.0
        if minAvg > threeAvg {
            minAvg = threeAvg
            result = i-2
        }

        //2개짜리 평균
        let twoAvg = Double(A[i-1] + A[i]) / 2.0 
        if minAvg > twoAvg {
            minAvg = twoAvg
            result = i-1
        }
    }

    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.