Codility lesson5_4 - MinAvgTwoSlice

요약

A배열의 연속된 정수 집합을 slice라고 할때 가장 작은 평균을 갖는 slice의 시작위치를 반환

 

아이디어

수학적 지식을 요구하는 문제

1. a < (a+b)/2 보다 크다면 a<b를 만족한다.

2. (a+b)/2 < (c+d)/2라면 (a+b)/2 < (a+b+c+d)/4 < (c+d)를 만족한다.

3. 이렇게 되면 (a+b)/2와 (a+b+c+d)/4를 비교할 필요가 없어지기 때문에 4개 이상의 집합의 평균을 구하는게 의미없다.

4. 다만 3개의 원소를 가지는 slice에서 예외의 경우가 발생할 수 있음 

   -> a b c d 는 각각 2 2 1 2이라하면 (a+b)/2 > (a+b+c)/3을 만족한다.

5. 원소가 2개 또는 3개인 케이스만 확인을 한다.

 

코드

 

int solution(vector<int> &A) {
	// write your code in C++14 (g++ 6.2.0)

	double minAvg = (A[0] + A[1]) / 2.0;
	double Avg = 0;
	int sol = 0;

	for (int i = 2; i < A.size(); i++) 
    {
		Avg = (A[i - 2] + A[i - 1] + A[i]) / 3.0;
		if (minAvg > Avg)
		{
			minAvg = Avg;
			sol = i - 2;
		}
		
		Avg = (A[i - 1] + A[i]) / 2.0;
		if (minAvg > Avg)
		{
			minAvg = Avg;
			sol = i - 1;
		}

	}

	return sol;
}

결과는 

 

우선 저도 수학적 지식으로 풀어내지 못했고 구글의 지식으로 풀어냈습니다. 헤헷

 

몇일간 이 문제로 고민을 했네요.

 

많은 사람들과 같이 처음의 아이디어는 O(N*N)방법을 생각습니다.

 

그런데 미디움 문제에서 이정도 퍼포먼스가 허용이 될리가 없어 라는 생각때문에 해당 방법의 코드는 제출안했습니다.

 

종이에 펜으로 써가면서 모든원소를 검사하지 않는 방법이 있을까 고민을 하고 알고리즘 이론도 많이 살펴봤는데

 

방법이 보이지 않아서 구글의 힘을 빌렸네요...

 

알고리즘 문제풀어 오면서 처음으로 수학적 지식으로 풀어내는 문제를 만났는데요.

 

이런문제들의 경험이 쌓여 결국 스스로 수학적 지식을 요구하는 문제를 풀어냈을때 얼마나 기분이 좋을지에 설레네요.

 

마지막으로 혹여나 아이디어에 써놓은 풀이가 이해가 안되시면 종이에 풀어가며 증명해보시면 이해가 빠르기때문에 

 

이런방법도 추천드립니다.