Codility - Lesson5 MinAvgTwoSlice

상세 문제는 여기서 확인 하시면 됩니다.

 

설명하자면 주어진 array에서 각 위치의 결과값들에 대한 평균값이 가장 작은 시작점을 구하는 것입니다. 글로 쓰고나서 읽어보니 저도 이해가 잘 안되므로 예제로 설명드리겠습니다.

A가 다음과 같을 때

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

(0,1)은 (4+2)/2 = 3이되 고 (0,3)은 (4+2+2+5)/4 = 3.25 가 됩니다. 그리고 (P,Q)라 했을때 P<Q입니다.

 

우선 생각나는데로 전체 비교를 해서 만들어봤습니다.

fun solution(A: IntArray): Int {
    val a_size = A.size
    var min = Int.MAX_VALUE
    var ans = 0
    for(i in 0 until  a_size-1){
        var count = 1
        var  sum = A[i]
        for( j in i+1 until a_size){
            count++
            sum +=A[j]
            var avg = sum/count
            if(min > avg){
                min = avg
                ans = i
            }
        }
    }
    return ans
}

 처음에는 결과가 자꾸 0이나와서 왜 그런가 했더니 , 문제에서 평균값이 소수점까지 비교를 하는거여서 그랬던 거였습니다. 그래서 변수 타입을 Double로 바꿔서 했더니 우선 결과는 정확하게 나왔지만 역시 예상대로 연산쪽에서 많은 시간을 잡아 먹었습니다. ( 복잡도 : O(N ** 2), 결과는 60%가 나왔습니다 )

 

아무리 머리를 써도 답을 몰라서 구글링을 해보니 이 문제를 풀려면 수학적인 지식이 쫌 필요한 문제였습니다.

 

 >2개의 평균값이 최소 평균이다.

>>배열 요소가 양수일 경우에만

 

 >음수로 범위를 넓히면 2개 또는 3개가 최소 평균이 된다.

>>3개가 최소가 되는 원리는 모르겠다.

 

그래서 풀이를 하면

fun solution(A: IntArray): Int {
    var minAvg = (A[0] + A[1]) / 2.0
    var ans = 0

    for (i in 2 until A.size) {
        var avg = (A[i - 2] + A[i - 1] + A[i]) / 3.0

        if (avg < minAvg) {
            minAvg = avg
            ans = i - 2
        }

        avg = (A[i - 1] + A[i]) / 2.0

        if (avg < minAvg) {
            minAvg = avg
            ans = i - 1
        }
    }
    return ans
}

이 됩니다.

 

정말 짜증나는 문제였습니다.

 

참고

https://woounnan.tistory.com/182

codility] MinAvgTwoSlice