비어 있지 않은 정수 배열 A가 주어진다. 배열의 길이는 N이다.
정수 쌍 (P, Q), 0 ≤ P < Q < N 인 경우를 배열 A의 "슬라이스(slice)"라고 한다.
(즉, 슬라이스는 최소 두 개 이상의 원소를 포함한다.)
슬라이스 (P, Q)의 평균은 (A[P] + A[P + 1] + ... + A[Q])의 합을 슬라이스의 길이로 나눈 값이다.
정확히는, 평균은 (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1) 이다.
예를 들어, 다음과 같은 배열 A가 주어진 경우:
A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8
다음과 같은 예시 슬라이스들이 존재한다:
- 슬라이스 (1, 2), 평균은 (2 + 2) / 2 = 2
- 슬라이스 (3, 4), 평균은 (5 + 1) / 2 = 3
- 슬라이스 (1, 4), 평균은 (2 + 2 + 5 + 1) / 4 = 2.5
목표는 평균이 최소인 슬라이스의 시작 위치를 찾는 것이다.
다음 함수를 작성하라:
class Solution { public int solution(int[] A); }
이 함수는 정수 배열 A가 주어졌을 때, 평균이 최소인 슬라이스의 시작 위치를 반환해야 한다.
만약 평균이 최소인 슬라이스가 둘 이상 존재한다면, 그 중 시작 위치가 가장 작은 값을 반환해야 한다.
예를 들어, 위 배열 A가 주어지면,
함수는 1을 반환해야 한다. (설명된 바와 같이 평균이 최소인 슬라이스의 시작 위치)
효율적인 알고리즘을 작성하라. 다음 조건을 만족해야 한다:
- N은 [2..100,000] 범위의 정수이다.
- 배열 A의 각 원소는 [−10,000..10,000] 범위의 정수이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
public class MinAvgTwoSlice
{
public int solution(int[] A)
{
float minAvg = float.MaxValue;
int maxRange = A.Length - 1;
int minStartIndex = 0;
// 슬라이스 = 연속된 구간 배열
// 최소 평균 슬라이스는 길이가 2 또는 3에서만 나온다.
// 길이 4 이상 구간의 평균은 결국 내부의 2~3 구간 평균 범위 안에 있기 때문.
// 왜? => 긴 구간 평균은 그 안에 포함된 짧은 구간 평균들의 가중평균이 되므로,
// 전체 평균이 더 작아지려면 이미 내부의 길이 2 또는 3 구간에서
// 최소 평균이 나타나게 된다.
// * 가중 평균 : 가중치를 가진 평균
for (int i = 0; i < maxRange; i++)
{
int sumLength2 = A[i] + A[i + 1];
float avgLength2 = GetAverage(sumLength2, 2);
if (avgLength2 < minAvg)
{
minAvg = avgLength2;
minStartIndex = i;
}
if (i + 2 >= A.Length)
continue;
int sumLength3 = A[i] + A[i + 1] + A[i + 2];
float avgLength3 = GetAverage(sumLength3, 3);
if (avgLength3 < minAvg)
{
minAvg = avgLength3;
minStartIndex = i;
}
}
return minStartIndex;
}
private float GetAverage(int sum, int length)
{
return (float)sum / length;
}
}
|
cs |