MinAvgTwoSlice (Codility)

문제

N개의 정수를 담은 컨테이너가 주어진다. 그리고 0<= P < Q < N 조건을 만족하는 P ~ Q 인덱스 범위에서의 평균값 중 가장 작은 값일때의 P를 구하는 문제이다.

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

다음과 같이 7개인 컨테이너가 있다. 0 <= P < Q < 7 범위에서 평균값을 구하다 보면

P ~ Q => 1 ~ 2 => (2 + 2) / 2 => 2

일때 가장 작은 평균값이 나오기 때문에 답은 P = 1 이다.

 

해결 방법

단순하게 위의 방법을 코드로 구현하여 접근한다면, 효율성이 떨어지게 된다. 이때 시간 복잡도는 O(N^2)이 나온다. O(N)이 나와야 효율성에서 통과가 되기 때문에, 다른 방법을 생각해야 한다.

 

평균값의 원리를 잘 알고 있다면, 다른 방법을 사용해 볼 수 있다.

 

평균값은 항상 평균값을 계산할 숫자중에 가장 작은 값보다 크거나 같다.  

예를들어 (1, 2, 3)이 있다면 (1 + 2 + 3) / 3 = 2로 가장 작은 값인 1보다 크다.  

 

이 뜻은 최소 범위에서의 평균값을 알고 있다면, 그 이후 범위의 평균값은 구할 필요가 없다는 것이다.

 

예를들어 보자. (1, 2, 3, 4)가 있다. 각각 두개씩 짝을 지어 평균값을 구한다.

(1, 2) = (1 + 2) / 2 = 3 / 2 = 1.5
(3, 4) = (3 + 4) / 2 = 7 / 2 = 3.5

이 평균값들의 평균값을 나타내면, 전체 평균값과 같다.

(1.5 + 3.5) / 2 = 5 / 2 = 2.5
(1 + 2 + 3 + 4) / 4 = 10 / 4 = 2.5

결국 최소 범위의 부분적인 평균값은 큰 범위의 평균값보다 작을 수 없다. 그러므로 최소 범위의 평균값 중 가장 작은 값이 특정 범위에서의 최소 평균값이 된다.

 

하지만 3개일 경우 예외가 있기 때문에 이 경우도 평균 값을 구해줘야 한다. (2, 6, 1)을 예로들어보자. 평균값을 최소 범위로 구해보면 다음과 같다.

(2, 6) => (2 + 6) / 2 => 4
(6, 1) => (6 + 1) / 2 => 3.5

(4, 3.5) => (4 + 3.5) / 2 = 3.75
(2, 6, 1) => (2 + 6 + 1) / 3 = 3

부분 평균값의 평균이 전체 범위의 평균값과 서로 다른 것을 볼 수 있다. 그렇기 때문에 3개 범위일때에도 평균값을 계산해줘야 한다.

 

코드는 다음과 같다.

int solution(vector<int>& A) 
{
	float min = (A[0] + A[1]) / 2.f;
	int result = 0;
	for (int i = 2; i < A.size(); ++i) 
	{
		float r = (A[i] + A[i - 1] + A[i - 2]) / 3.f; // 3개 범위일때 평균값
		if (r < min) // 가장 작은 평균 값일 경우 P의 값을 갱신한다.
		{
			min = r;
			result = i - 2;
		}
		r = (A[i] + A[i - 1]) / 2.f; // 2개 범위일때 평균값
		if (r < min)
		{
			min = r;
			result = i - 1;
		}
	}
	return result;
}